Codeforces Round #241 (Div. 2) D

本文主要是介绍Codeforces Round #241 (Div. 2) D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：D. Population Size

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

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

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

#include <stdio.h>
#include <string.h>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 < n) {i++;}if (i == n) {ans++;break;}__int64 e = i, d;if ((a[e] - a[s]) % (e - s) == 0) {d = (a[e] - a[s]) / (e - s);}else {ans++;continue;}if (d > 0 && s1 > (a[s] - 1) / d) {ans++;i = e;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;
}

这篇关于Codeforces Round #241 (Div. 2) D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---