Codeforces Round #241 (Div. 2) D

题目链接：D. Population Size 题意：一些数字，要求分块，使得每一块都是等差数列，但是有些数字是-1，代表任意数字（但是要大于0），问最少需要分几块。 思路：贪心。每次找到相邻两个确定数字，并且记录下第一个数字前有多少个-1，就能确定出公差，然后利

题目链接：D. Population Size

题意：一些数字，要求分块，使得每一块都是等差数列，但是有些数字是-1，代表任意数字（但是要大于0），问最少需要分几块。

思路：贪心。每次找到相邻两个确定数字，并且记录下第一个数字前有多少个-1，就能确定出公差，然后利用公差去判断前面的-1能不能填进去，如果不能ans就多1，然后从第二个确定数字位置开始找，如果可以，就利用公差一直找到能放的最后一个位置，然后下次从那个位置开始找。

细节比较多，代码挫挫的:

#include #include const int N = 200005;__int64 n, i, j;__int64 a[N];int main() {	__int64 ans = 0;	scanf("%I64d", &n);	for (i = 0; i < n; i++)		scanf("%I64d", &a[i]);	i = 0;	__int64 s1 = 0;	while (i < n) {		s1 = 0;		while (a[i] == -1 && i < n) {			s1++;			i++;		}		__int64 s = i;		if (i < n)			i++;		while (a[i] == -1 && i  0 && s1 > (a[s] - 1) / d) {			ans++;			i = e;	<p>本文来源gao!daima.com搞$代!码#网#</p>		continue;		}		__int64 sum = a[s];		for (j = s + 1; j < n; j++) {			sum += d;			if (sum < 1) {				i = j;				ans++;				break;			}			if (a[j] != -1 && sum != a[j]) {				i = j;				ans++;				break;			}		}		if (j == n) {			i = n;			ans++;		}	}	printf("%I64d\n", ans);	return 0;}

喜欢 (0)赏

[搞代码]

分享 (0)