CF405D Toy Sum

本文主要是介绍CF405D Toy Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

刚看见的时候貌似是一道很难做的题…题面十分的玄学,不能重选的要求也十分难搞…

但是,可以发现N<=5*10⁵从中可以不难发现一旦不能直接取时便会一定有一对正好和为1e6-1

#include<bits/stdc++.h>
using namespace std;
const int maxS=1000005;
int a[maxS],b[maxS],answer[maxS],S,N;
bool boo[maxS];
int main()
{S=1000000;scanf("%d",&N);int i;for(i=1;i<=N;i++){scanf("%d",&a[i]);boo[a[i]]=1;//不能选了}int cnt=0;int full=0;//成对不能选的个数for(i=1;i<=N;i++)if(!boo[S-a[i]+1])//直接取{answer[++cnt]=S-a[i]+1;boo[S-a[i]+1]=1;}elsefull++;full/=2;//计算了两次..for(i=1;i<=(S+1)/2;i++)if(!boo[i]&&!boo[S-i+1])//成对可以取的{if(!full)break;//不需要了full--;answer[++cnt]=i;answer[++cnt]=S-i+1;}printf("%d\n",cnt);//输出个数for(i=1;i<=cnt;i++)printf("%d ",answer[i]);//输出序列return 0;
}

算是一道小清新的构造题…吧…

这篇关于CF405D Toy Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---