Codeforces 402B Trees in a Row：等差數列構建與最少修改次數動態規劃解法

題目大意

有 n 棵樹，高度 a[i]。需修改部分樹高，使最終序列形成公差為 k 的嚴格遞增等差數列（即 b[i] = b[0] + i*k）。一次操作可將一棵樹改為任意高度。求最少操作次數，並輸出一組可行修改方案。

核心觀察

保持不變的樹必須滿足 a[i] = base + i*k，即 base = a[i] - i*k。
問題轉化為：找出一個 base，使得滿足 a[i] - i*k = base 的下標 i 數量最大化。
最少修改次數 = n - max_freq。

演算法流程

1. 遍歷 i = 0..n-1，計算 val = a[i] - i*k。
2. 用哈希表 unordered_map 統計每個 val 的出現次數，記錄最大頻次 max_freq 及對應 base。
3. 最少操作數 = n - max_freq。
4. 構建目標序列 target[i] = base + i*k，對比 a[i] 輸出修改操作。

完整代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; long long k;
    cin >> n >> k;
    vector a(n);
    for (int i=0; i> a[i];
    unordered_map freq;
    long long bestBase = 0;
    int maxFreq = 0;
    for (int i=0; i maxFreq) { maxFreq = f; bestBase = base; }
    }
    cout << n - maxFreq << '\n';
    for (int i=0; i