【贪心】【multiset】Tinkoff Challenge

考虑两个人，先把各自的集合排个序，丢掉一半，因为比较劣的那一半一定用不到。

然后贪心地放，只有两种决策，要么把一个最优的放在开头，要么把一个最劣的放在结尾。

如果我的最优的比对方所有的都劣（或等于），我就把我最劣的往结尾放。否则我把我最优的往开头放。

用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]='';
	puts(s3+1);
	return 0;
}