CodeforcesRound#241(Div.2)D

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#241(Div.2)D，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1434字，纯文字阅读大概需要3分钟。

内容图文

题目链接：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;
}

内容总结

以上是互联网集市为您收集整理的CodeforcesRound#241(Div.2)D全部内容，希望文章能够帮你解决CodeforcesRound#241(Div.2)D所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端