Codeforces 416D Population Size(贪心)

题目连接：Codeforces 416D Population Size

题目大意：给出一个序列，求最少可以划分成几个子的等差序列，-1代表任意值，但是一定要大于0.

解题思路：贪心，首先明确如果当前的数能够合进前一个序列，那么绝对不会让它留到下一个序列去考虑。

遍历，对于每个数进行判断，看是否可以并到前一个等差序列。首先先找到最前两个不为任意值的数，判断是否可以组成等差数列（因为会有-1干扰， -1 1 2，ans = 2），判断是否能组成，则要记录第一个数前面有几个-1，确定公差后会不会导致前面任意值变成负数。然后确定公差之后，只需要记录公差和前一项的值即可，如果新的数不能并入序列，则新开序列，按照上面的方法重新计算。

#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(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;
}

Codeforces 416D Population Size(贪心),布布扣,bubuko.com

Codeforces 416D Population Size(贪心)

原文：http://blog.csdn.net/keshuai19940722/article/details/23730913