http://codeforces.com/contest/794/problem/C
题意:
有两个人要为公司起名字,每个人手中都有n个字符,现在要取一个n个字符长度的公司名。两人轮流取名,每次选择一个字符,可以任意选择放在1~n还未放置字符的位置上,每个字符限用一次。
现在第一个人希望公司名字典序越小越好,而第二个人希望字典序越大越好。输出最后的公司名。
思路:
首先肯定是要排序的,第一个人肯定去用前面最小的几个,而第二个人肯定去用前面最大的几个。
轮到第一个人时,我们首先将他手中最小的字符和第二个人手中最大的字符相比,如果此时最小字符大于等于了第二个人的最大字符,那么此时就把最大的字符放置最末尾。否则的话就把最小的放到首位。
轮到第二个人时同理分析。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
typedef long long LL; const int maxn=*1e5+; char s1[maxn],s2[maxn];
char ans[maxn]; bool cmp1(char a,char b)
{
return a<b;
} bool cmp2(char a,char b)
{
return a>b;
} int main()
{
//freopen("D:\\input.txt","r",stdin);
while(cin>>s1>>s2)
{
int len=strlen(s1);
sort(s1,s1+len,cmp1);
sort(s2,s2+len,cmp2);
int p_left=;
int p_right=len/+(len&)-;
int q_left=;
int q_right=len/-;
int l=,r=len-;
int flag=;
for(int i=;i<len;i++)
{
if(flag)
{
if(s1[p_left]>=s2[q_left]) ans[r--]=s1[p_right--];
else ans[l++]=s1[p_left++];
flag=;
}
else
{
if(s2[q_left]<=s1[p_left]) ans[r--]=s2[q_right--];
else ans[l++]=s2[q_left++];
flag=;
}
}
for(int i=;i<len;i++)
printf("%c",ans[i]);
}
return ;
}