题解：P11581 [CCC2020] Surmising a Sprinter's Speed

bilibili_daogu · 2025-01-18 21:19:37 · 题解

首先出场的是

code：

#include <bits/stdc++.h>
using namespace std;

struct node //  定义一个结构体node，包含两个成员变量t和p
{
    int t, p;
} a[100001];

bool cmp(node x, node y)
{
    return x.t < y.t;
}

int n; //  定义一个整数变量n，表示输入的节点数
double ans, v = 0; //  定义两个浮点数变量ans和v，分别用于存储最大速度和当前速度

int main()
{
    cin >> n; //  输入节点数
    for (int i = 1; i <= n; i++)
        cin >> a[i].t >> a[i].p; //  输入每个节点的t和p值
    sort(a + 1, a + n + 1, cmp); //  按照t值对节点进行排序
    for (int i = 1; i < n; i++)
    {
        v = abs(a[i].p - a[i + 1].p) / 1.0 / (a[i + 1].t - a[i].t); //  计算相邻节点之间的速度
        ans = max(ans, v); //  更新最大速度
    }
    printf("%.6lf", ans); //  输出最大速度，保留6位小数
    return 0;
}

思路：

1. 结构体定义：

   struct node {
      int t, p;
   } a[100001];

   这里定义了一个结构体 node，它包含两个整数成员 t 和 p。数组 a 用于存储 n 个 node 结构体。

2. 比较函数：

   bool cmp(node x, node y) {
      return x.t < y.t;
   }

   这个比较函数用于排序。它将根据 node 结构体的 t 成员对节点进行升序排序。

3. 主函数：

   int main() {
      cin >> n;
      for (int i = 1; i <= n; i++) cin >> a[i].t >> a[i].p;
      sort(a + 1, a + n + 1, cmp);
      for (int i = 1; i < n; i++) {
          v = abs(a[i].p - a[i + 1].p) / 1.0 / (a[i + 1].t - a[i].t);
          ans = max(ans, v);
      }
      printf("%.6lf", ans);
      return 0;
   }

   • 首先读取输入的 n，表示序列的长度。
   • 然后读取 n 个 node 结构体的数据，每个结构体包含两个整数 t 和 p。
   • 使用 sort 函数对结构体数组 a 进行排序，排序依据是 t 成员。
   • 接着，遍历排序后的数组，计算相邻点之间的斜率。斜率计算公式为： [ v = \frac{|a[i].p - a[i+1].p|}{a[i+1].t - a[i].t} ] 这里使用 abs 函数来确保斜率为正数。
   • 使用 max 函数更新最大斜率 ans。
   • 最后我们可以，输出最大斜率 ans，保留六位小数。