Codeforces 416D Population Size(貪心)

題目連接：Codeforces 416D Population Size

題目大意：給出一個序列，求最少可以劃分成幾個子的等差序列，-1代表任意值，但是一定要大於0.

解題思路：貪心，首先明確如果當前的數能夠合進前一個序列，那麼絕對不會讓它留到下一個序列去考慮。

遍歷，對於每個數進行判斷，看是否可以並到前一個等差序列。首先先找到最前兩個不為任意值的數，判斷是否可以組成等差數列（因為會有-1干擾， -1 1 2，ans = 2），判斷是否能組成，則要記錄第一個數前面有幾個-1，確定公差後會不會導致前面任意值變成負數。然後確定公差之後，只需要記錄公差和前一項的值即可，如果新的數不能並入序列，則新開序列，按照上面的方法重新計算。

#include 
#include 
#include 

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

void set(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) {
			if (pl < 0)
				cnt++;
			else if (pr < 0)
				continue;
			else if (cur + d > 0)
				cur = cur + d;
			else {
				set(-1, 0, 1);
				pr = -1;
				ans++;
			}
		} else {
			if (pl < 0) {
				set(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(i, a, 0);
					ans++;
				} else {
					pr = i;
					cur = a;
				}
			} else {
				if (cur + d == a)
					cur = a;
				else {
					set(i, a, 0);

					pr = -1;
					ans++;
				}
			}
		}
	}
	cout << ans + 1<< endl;
	return 0;
}