Codeforces 538C Tourist's Notes：貪心求最大可能高度

題目描述

n 天徒步，相鄰天高度差 ≤ 1。已知 m 個記錄 (d_i, h_i)（按天遞增）。求全程最大可能高度，或判定記錄矛盾。n ≤ 1e8, m ≤ 1e5。

關鍵觀察

兩個已知點 (d1, h1), (d2, h2) 之間，最大高度出現在中間最高點。兩點間天數 dt = d2 - d1，高度差 dh = |h2 - h1|。若 dh > dt 則矛盾（IMPOSSIBLE）。否則，中間可先升後降，峰值高度 = max(h1, h2) + (dt - dh) / 2。

邊界段落處理

• 第一天到第一個記錄：可從 h1 開始每天 +1，最大高度 = h1 + (d1 - 1)。
• 最後記錄到第 n 天：同理 hm + (n - dm)。

C++ 代碼實現

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

int main() {
    long long n; int m; cin >> n >> m;
    long long d1, h1; cin >> d1 >> h1;
    long long ans = h1 + (d1 - 1); // 首段
    bool ok = true;
    for (int i = 2; i <= m; ++i) {
        long long d2, h2; cin >> d2 >> h2;
        long long dt = d2 - d1, dh = abs(h2 - h1);
        if (dh > dt) { ok = false; break; }
        ans = max(ans, max(h1, h2) + (dt - dh) / 2);
        d1 = d2; h1 = h2;
    }
    if (ok) ans = max(ans, h1 + (n - d1)); // 尾段
    if (ok) cout << ans << endl;
    else cout << "IMPOSSIBLE" << endl;
    return 0;
}

複雜度

• 時間：O(m)。
• 空間：O(1)。