HDU 4393 Throw nails（暴力前502秒 + 排序優化）

HDU 4393 Throw nails - 暴力模擬前 502 秒 + 排序

n ≤ 50,000 名選手，每人首秒速度 F，之後每秒速度 S。每秒末尾向當前最遠選手跑道扔釘子淘汰。輸出每秒被淘汰選手 ID。

關鍵觀察

F ≤ 500，S ≤ 100。經過 501 秒後，首秒速度優勢消失，排名完全由穩態速度 S 決定。因此：

• 前 502 秒：暴力模擬每秒找最大距離
• 第 503 秒起：按 502 秒時距離排序，直接輸出

完整代碼實現

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 50005;
const int INF = 0x3f3f3f3f;

struct Player {
    int f, s, d, id;
} p[MAXN];

bool cmp(const Player& a, const Player& b) {
    if (a.d != b.d) return a.d > b.d;
    return a.id < b.id;
}

int main() {
    int T; scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &p[i].f, &p[i].s);
            p[i].id = i; p[i].d = 0;
        }
        
        printf("Case #%d:\n", tc);
        
        // 第 1 秒
        int best = 0, pos = 0;
        for (int i = 1; i <= n; i++) {
            p[i].d += p[i].f;
            if (p[i].d > best) { best = p[i].d; pos = i; }
        }
        p[pos].d = INF;
        printf("%d", pos);
        
        // 第 2~502 秒
        for (int sec = 2; sec <= min(n, 502); sec++) {
            best = 0; pos = 0;
            for (int i = 1; i <= n; i++) {
                if (p[i].d == INF) continue;
                p[i].d += p[i].s;
                if (p[i].d > best) { best = p[i].d; pos = i; }
            }
            p[pos].d = INF;
            printf(" %d", pos);
        }
        
        // 第 503 秒起：按距離排序
        sort(p+1, p+n+1, cmp);
        for (int i = 503; i <= n; i++)
            printf(" %d", p[i].id);
        printf("\n");
    }
    return 0;
}

複雜度分析

• 前 502 秒：O(502 × n) ≈ 2.5e7，邊界但可行
• 排序：O(n log n)
• 優化：實際可只模擬前 min(n, 502) 秒

避坑指南

• 同距離時 ID 小優先（cmp 中處理）
• 被淘汰選手標記距離 = INF，不再參與比較
• 輸出格式：Case #x: 換行，第二行空格分隔
• 大數據用 scanf/printf