大意: 给定$n$元素序列$a$, 求将$a$划分为连续的等差数列, 且划分数尽量小. $a$中的$-1$表示可以替换为任意正整数, 等差数列中必须也都是正整数.
贪心策略就是从前到后尽量添进一个等差数列中, 否则就再新增一个等差数列.
这种模拟题最好还是写个递归, 思路会清晰一些
#include <iostream>
#include <algorithm>
#include <cstdio>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll; const int N = 1e6+10;
int n;
ll a[N]; int solve(int l) {
int p[2]{};
REP(i,l,n) if (a[i]>0) {
if (!p[0]) p[0]=i;
else if (!p[1]) p[1]=i;
else break;
}
if (!p[1]) return 1;
if ((a[p[1]]-a[p[0]])%(p[1]-p[0])) return 1+solve(p[1]);
int d = (a[p[1]]-a[p[0]])/(p[1]-p[0]);
PER(i,l,p[0]-1) {
a[i] = a[i+1]-d;
if (a[i]<=0) return 1+solve(p[1]);
}
REP(i,p[1]+1,n) {
ll t = a[i-1]+d;
if (t<=0) return 1+solve(i);
if (a[i]<=0) a[i]=t;
else if (a[i]!=t) return 1+solve(i);
}
return 1;
} int main() {
scanf("%d", &n);
REP(i,1,n) scanf("%lld", a+i);
printf("%d\n", solve(1));
}