CF794C Naming Company 题解

· · 题解

题目链接
在我的Blog查看

题目大意

A,B 两人各有一个长度为 n 的，由小写字母构成的字符串 s,t，还有一个长度为 n，初始时由 ? 组成的目标串 f。

现在，A和B轮流进行如下操作：

  1. 在自己的字符串中选出一个字符 x。
  2. 将 f 中的一个 ? 替换为 x。
  3. 将 x 从自己的字符串中删去。 当 f 中没有 ? 时游戏结束。

A 的目标是让 f 的字典序尽量小，而 B 的目标是让字典序尽量大。
现在设 A 为先手，你需要求出游戏结束后的 f。

注意：s,t 中可能有多个重复的字符，每次只删除一个。

解题思路

一个显而易见的贪心思路，分别让 s,t 升序和降序排序。
然后，每个人尽可能把自己字符串中前面的字符放在 f 的前面，从而最大/最小化 f 的字典序。

如果你是这么写的话，恭喜你 WA on test 6。

这里来举一个反例：

s="pqrs"
t="dcba"

如果在这种情况下，还是按照上面的方法，那你会发现 A,B 在互相帮助QwQ。也就是说，两方的操作会对对方的目标产生好处。
那么，我们的最优方案就变成了止损。由于在字符串越前面的字符，对字典序的影响就越大，所以，我们就尽可能地把对对方有利的字符往后放。
比如对于这组数据，A 就需要尽可能地把字典序大的字母往 f 的后面放，B 同理。

最后，我们将两个思路结合：
当 s_i<t_i 时，按第一种方法贪心。
否则，就按第二种方法贪心。

有一些实现上的小细节，这里就不写了，直接上代码。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int Maxn=3e5+10;
char s[Maxn];
int a[Maxn],b[Maxn];
int f[Maxn];
int n;
inline bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    // freopen("in.txt","r",stdin);
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;++i)
    a[i]=s[i]-'a';
    scanf("%s",s+1);
    for(int i=1;i<=n;++i)
    b[i]=s[i]-'a';
    sort(a+1,a+1+n);
    sort(b+1,b+1+n,cmp);
    int x=0,y=0,pos=n;
    for(int i=1;i<=n;++i)
    {
        if(a[x+1]>=b[y+1]){pos=i-1;break;}
        if(i & 1)f[i]=a[++x];
        else f[i]=b[++y];
    }
    x=y=(n>>1)+1;
    if((n & 1))++x;
    for(int i=n;i>pos;--i)
    {
        if((pos+(n-i+1)) & 1)f[i]=a[--x];
        else f[i]=b[--y];
    }
    for(int i=1;i<=n;++i)
    putchar(f[i]+'a');
    putchar('\n');
    return 0;
}