HDU 5078 Osu!：最大跳躍難度計算

題目大意

Osu! 遊戲中，N 個點依次出現，點 i 在時間 t_i 位置 (x_i, y_i)。跳躍難度 = 相鄰兩點距離 / 時間差。求整場遊戲的最大難度。N ≤ 1000，t ≤ 10^6。

解法

直接遍歷計算相鄰點難度，取最大值：

ans = max( sqrt((x_i-x_{i-1})² + (y_i-y_{i-1})²) / (t_i - t_{i-1}) )

關鍵點

• 時間嚴格遞增，分母非零
• 距離用 double 計算，輸出精度 1e-9
• 鞍山現場賽簽到題，極簡單

完整代碼

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 1010;
long long t[MAXN];
double x[MAXN], y[MAXN];

int main() {
    int T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> t[i] >> x[i] >> y[i];
        double ans = 0;
        for (int i = 1; i < n; i++) {
            double dx = x[i] - x[i-1];
            double dy = y[i] - y[i-1];
            double dist = sqrt(dx*dx + dy*dy);
            double diff = t[i] - t[i-1];
            ans = max(ans, dist / diff);
        }
        printf("%.10f\n", ans);
    }
    return 0;
}

複雜度分析

O(N) 每測試用例，極快。