本文主要是介绍CodeForces 416D Population Size，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
一串数字 有一些元素可以替换成任何正数 问 最少用几个等差数列可以覆盖整串数字
思路：
贪心 分类讨论
假设a[x]和a[y]两个数字是已知的 那么我们先判断他们两个中间可否形成等差数列
如果不行 则 让x到y-1形成一个等差数列
如果行 再判断a[x]是否已经在前面的一个等差数列中
如果不在 那么用a[y]和a[x]求出公差 看是否能够满足x前的所有未知数字
如果满足 则 a[x]和a[y]可以分在一组
如果不满足 则 让x到y-1分一组
如果在 判断a[y]和a[x]求出的公差是否和前面的公差相等
如果相等 就放在一组
如果不等 让a[x]的组尽量往后延伸（即消耗尽量多的未知数）
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 200010
#define oo 10000000000LLint ans,n;
__int64 a[M];
__int64 cha=oo;int main()
{int i,j,first,second;scanf("%d",&n);for(i=1,first=second=0;i<=n;i++){scanf("%I64d",&a[i]);if(a[i]!=-1){if(second){if(!first) first=i;}else second=i;}}if(!first){puts("1");return 0;}if( (a[first]-a[second])%(first-second) || a[first]-(a[first]-a[second])/(first-second)*(first-1)<=0 ){ans=2;cha=oo;}else{ans=1;cha=(a[first]-a[second])/(first-second);}for(j=first-1;j>=1;j--) a[j]=0;for(i=first+1;i<=n;i++){if(a[i]!=-1){if((a[i]-a[first])%(i-first)){ans++;if(cha!=oo){for(j=first+1;j<=n;j++){if(a[j]!=-1||a[j-1]+cha<=0) break;a[j]=a[j-1]+cha;}}else{for(j=i-1;j>=first;j--) a[j]=0;}first=i;cha=oo;}else{if(cha==oo){cha=(a[i]-a[first])/(i-first);for(j=first-1;j>=1;j--){if(a[j]!=-1||a[j+1]-cha<=0) break;a[j]=a[j+1]-cha;}if(a[j]==-1){ans++;cha=oo;for(j=i-1;j>=first;j--) a[j]=0;}else{for(j=i+1;j<=n;j++){if(a[j]!=-1||a[j-1]+cha<=0) break;a[j]=a[j-1]+cha;}}first=i;}else{if(cha==(a[i]-a[first])/(i-first)){for(j=first+1;j<i;j++) a[j]=0;first=i;}else{ans++;for(j=first+1;j<i;j++){if(a[j]!=-1||a[j-1]+cha<=0) break;a[j]=a[j-1]+cha;}first=i;cha=oo;}}}}}if(cha<0){for(j=first+1;j<=n;j++){if(a[j-1]+cha<=0){ans++;break;}a[j]=a[j-1]+cha;}}printf("%d\n",ans);return 0;
}
这篇关于CodeForces 416D Population Size的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
