本文主要是介绍Codeforces Round #268 (Div. 1) B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
B. Two Sets
题意：n个不相同的数p1~pn，把它们划分为两个集合。必须满足如果pi在集合0中，a-pi也在集合0中；如果pi在集合1中，b-pi也在集合1中。
思路：先排序，然后贪心从两边开始构造。两个指针l和r，指向未构造区间的左边和右边。如果pl和pr能放在一个集合中，就把它们放到一个集合。如果不行，就为pl找一个合适的（用二分查找），必须放在a和b中较小那个数的集合，找不到适合的数的话就是无解。因为pl和pr放不进max(a,b)那个集合，其他数就算放进去了，pr也是无解，所以只需要考虑min(a,b)那个集合。比赛的时候我跪在了n=1的情况，坑啊。。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <ctype.h> using namespace std; int num[100010];
int ha[100010];
int rnk[100010];int cmp(int a,int b){return num[a]<num[b];
}int find(int x,int l,int r){int mid;while(1){mid=(l+r)/2;if(num[rnk[mid]]==x)return mid;if(l==r)return -1;if(num[rnk[mid+1]]==x)return mid+1;if(l+1==r)return -1;if(num[rnk[mid]]>x){r=mid;}else{l=mid;}}
}int main(){int n,a,b;while(cin>>n>>a>>b){memset(ha,-1,sizeof(ha));for(int i=1;i<=n;i++){scanf("%d",&num[i]);rnk[i]=i;}sort(rnk+1,rnk+n+1,cmp);if(n==1){if(num[1]*2==a){cout<<"YES"<<endl;cout<<0;break;}if(num[1]*2==b){cout<<"YES"<<endl;cout<<1;break;}cout<<"NO"<<endl;break;}int l=1;int r=n;bool ok=1;while(1){bool brk=0;while(ha[rnk[l]]!=-1){if(l>=r){brk=1;break;}l++;}while(ha[rnk[r]]!=-1){if(l>=r){brk=1;break;}r--;}if(brk)break;if(num[rnk[l]]+num[rnk[r]]==a){ha[rnk[l]]=ha[rnk[r]]=0;l++; r--;continue;}if(num[rnk[l]]+num[rnk[r]]==b){ha[rnk[l]]=ha[rnk[r]]=1;l++; r--;continue;}//int fl=find( min(a,b)-num[rnk[l]],l,r);if( fl ==-1 || ha[rnk[fl]]!=-1 ){ok=0;break;}if( num[rnk[l]]+num[rnk[fl]]==a ){ha[rnk[l]]=0;ha[rnk[fl]]=0;}if( num[rnk[l]]+num[rnk[fl]]==b ){ha[rnk[l]]=1;ha[rnk[fl]]=1;}}if(ok){cout<<"YES"<<endl;for(int i=1;i<=n;i++){cout<<ha[i]<<" ";}}else{cout<<"NO"<<endl;}}return 0;
}
这篇关于Codeforces Round #268 (Div. 1) B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
