首页 > 代码库 > 【贪心】【multiset】Tinkoff Challenge - Final Round (Codeforces Round #414, rated, Div. 1 + Div. 2) C. Naming Company
【贪心】【multiset】Tinkoff Challenge - Final Round (Codeforces Round #414, rated, Div. 1 + Div. 2) C. Naming Company
考虑两个人,先把各自的集合排个序,丢掉一半,因为比较劣的那一半一定用不到。
然后贪心地放,只有两种决策,要么把一个最优的放在开头,要么把一个最劣的放在结尾。
如果我的最优的比对方所有的都劣(或等于),我就把我最劣的往结尾放。否则我把我最优的往开头放。
用multiset维护两人的集合即可。
#include<cstdio> #include<cstring> #include<algorithm> #include<set> using namespace std; int n; char s1[300010],s2[300010],s3[300010]; multiset<char>S1,S2; multiset<char>::iterator it; bool cmp(const char &a,const char &b){ return a>b; } int main(){ // freopen("c.in","r",stdin); scanf("%s%s",s1+1,s2+1); n=strlen(s1+1); sort(s1+1,s1+n+1); sort(s2+1,s2+n+1,cmp); for(int i=1;i<=n/2;++i){ S1.insert(s1[i]); S2.insert(s2[i]); } if(n&1){ S1.insert(s1[n/2+1]); } int head=1,tail=n; for(int i=1;i<=n;++i){ if(i==n && (n&1)){ s3[head++]=*S1.begin(); break; } char x1=*S1.begin(); it=S2.end(); --it; char x2=*it; if(i&1){ if(x1<x2){ s3[head++]=x1; S1.erase(S1.begin()); } else{ it=S1.end(); --it; s3[tail--]=*it; S1.erase(it); } } else{ if(x1<x2){ s3[head++]=x2; S2.erase(it); } else{ s3[tail--]=*S2.begin(); S2.erase(S2.begin()); } } } s3[n+1]=‘\0‘; puts(s3+1); return 0; }
【贪心】【multiset】Tinkoff Challenge - Final Round (Codeforces Round #414, rated, Div. 1 + Div. 2) C. Naming Company
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。