Codeforces 416D Population Size：貪心分割等差數列

問題描述

給定長度 n 的序列（含 -1 代表任意正整數），求最少分成幾個連續子段，使每段皆為等差數列（公差固定，項值 > 0）。

貪心策略

遍歷序列，嘗試將當前數併入前一個等差數列。核心邏輯：

1. 記錄前兩個非 -1 的數，確定公差 d
2. 檢查公差是否導致前面的 -1 變為非正數
3. 確定公差後，只需記錄前一項值與 d，新數若符合 cur + d == a 則併入，否則開新段

程式碼實作

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef long long ll;
ll n, a, pl, pr, val, cnt, ans, d, cur;

void set_new(ll pos, int value, int count) {
    pl = pos; val = value; cnt = count;
}

int main() {
    pl = pr = -1;
    ans = cnt = 0;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a;
        if (a < 0) { // -1 任意值
            if (pl < 0) cnt++;
            else if (pr < 0) continue;
            else if (cur + d > 0) cur += d;
            else { set_new(-1, 0, 1); pr = -1; ans++; }
        } else {
            if (pl < 0) { set_new(i, a, cnt); }
            else if (pr < 0) {
                ll sum = a - val;
                d = sum / (i - pl);
                if (val + (i-pl)*d != a || val <= cnt * d) {
                    set_new(i, a, 0); ans++;
                } else { pr = i; cur = a; }
            } else {
                if (cur + d == a) cur = a;
                else { set_new(i, a, 0); pr = -1; ans++; }
            }
        }
    }
    cout << ans + 1 << endl;
    return 0;
}

關鍵變數說明

• pl, pr：當前段第一個、第二個非 -1 位置
• val：第一個非 -1 的值
• d：公差
• cur：當前段最後一項值
• cnt：段首 -1 的個數