题目链接：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 < 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; }
Copyright © 2019-2025 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
