ZOJ 2938 Rock Skipping - 暴力枚舉模擬石頭跳水軌跡

ZOJ 2938 Rock Skipping - 暴力枚舉模擬石頭跳水軌跡

題目大意

水面上有若干石頭，初始位置不同。石頭被扔出後，每次跳躍間隔固定距離 dd，直到超出邊界。每次跳躍計為一次「跳」。給定所有石頭的初始位置 pos、跳躍間隔 dd，求：

1. 跳躍次數最多的石頭（num 最大）
2. 若並列，最終位置 last 最大者優先
3. 再並列，初始位置 pos 最大者優先
4. 再並列，間隔 dd 最大者優先

輸出獲勝石頭的參數。

暴力模擬算法

數據範圍較小（石頭數 ≤ 100，位置 ≤ 10000），直接模擬每顆石頭的跳躍過程：

struct Stone {
    int pos;    // 初始位置
    int dd;     // 跳躍間隔
    int num;    // 跳躍次數
    int last;   // 最後位置
};

int simulate(Stone &s, int boundary) {
    s.num = 0;
    s.last = s.pos;
    int cur = s.pos;
    while (true) {
        cur += s.dd;
        if (cur > boundary) break;  // 超出邊界停止
        s.num++;
        s.last = cur;
    }
    return s.num;
}

比較器實現

bool cmp(const Stone &a, const Stone &b) {
    if (a.num != b.num) return a.num > b.num;       // 次數優先
    if (a.last != b.last) return a.last > b.last;   // 最後位置優先
    if (a.pos != b.pos) return a.pos > b.pos;       // 初始位置優先
    return a.dd > b.dd;                             // 間隔優先
}

完整 AC 代碼

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

struct Stone {
    int pos, dd, num, last;
};

int main() {
    int n, boundary;
    while (scanf("%d%d", &n, &boundary) == 2) {
        vector stones(n);
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &stones[i].pos, &stones[i].dd);
        }
        
        for (auto &s : stones) {
            s.num = 0;
            s.last = s.pos;
            int cur = s.pos;
            while (true) {
                cur += s.dd;
                if (cur > boundary) break;
                s.num++;
                s.last = cur;
            }
        }
        
        sort(stones.begin(), stones.end(), [](const Stone &a, const Stone &b) {
            if (a.num != b.num) return a.num > b.num;
            if (a.last != b.last) return a.last > b.last;
            if (a.pos != b.pos) return a.pos > b.pos;
            return a.dd > b.dd;
        });
        
        printf("%d %d %d %d\n", 
               stones[0].pos, stones[0].dd, stones[0].num, stones[0].last);
    }
    return 0;
}

複雜度分析

• 模擬單顆石頭：O(boundary / dd)，最壞 O(boundary)
• 總體：O(n × boundary)，n≤100, boundary≤10000 即 10^6 量級，極快
• 排序：O(n log n) 可忽略

邊界情況處理

1. 初始位置已超出邊界：num=0, last=pos
2. 間隔 dd=0：無限循環，題目保證 dd>0 或需特判
3. 多組測試用例：while(scanf(...)==2) 循環讀入