本文共 1439 字，大约阅读时间需要 4 分钟。

$怎么说呢?这题还是很有迷惑性的$

比较容易想到的做法肯定是每次拿a串最小的字母构造字典序最小

每次拿b串最大的字母构造字典序最大

$那么假设当前q为a串最小字母,w为b串最大字母$

$Ⅰ.构造字典序最小时:q<=w,尽量往左边放$

$如果q>w,说明b串后面的字母都很小,那就尽量往右边放置$

$Ⅱ.构造字典序最大时:和上面思路一样,只是顺序反一下$

看起来显然的贪心策略,居然是错的!!!

$当a串是abc,b串是aaa时构造的名字是aab$

$此时就是因为a串先把b放在了末尾,然后前两个位置就都是a$

$所以应该提前取出a串要放的(len+1)/2个最小的字母$

$取出b串要放的len/2个字母$

$当a串比较大的时候,肯定是拿最大的字母放到末尾,因为迟早要放$

#include 
   
    using namespace std;const int maxn=3e5+10;char a[maxn],b[maxn],ans[maxn];int main(){	cin >> (a+1) >> (b+1);	int len=strlen(a+1);	sort(a+1,a+1+len);	sort(b+1,b+1+len);	reverse(b+1,b+1+len);	int l1=1,l2=1,r1=(len+1)/2,r2=len/2,l=1,r=len;	for(int i=1;i<=len;i++)	{		if(i%2==1)		{			if(a[l1]
    
     a[l1])	ans[l++]=b[l2++];//b大,肯定放前面 			else	ans[r--]=b[r2--];		}		}	cout<<(ans+1);}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/107223938 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！