CF794C Naming Company 题解

题目链接：CF794C Naming Company

题意：

下面是修正后的文本，使用Markdown格式和行内公式：

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

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

1. 在自己的字符串中选出一个字符 $x$。
2. 将 $f$ 中的一个 ? 替换为 $x$。
3. 将 $x$ 从自己的字符串中删去。

当 $f$ 中没有 ? 时游戏结束。

A 的目标是让 $f$ 的字典序尽量小，而 B 的目标是让字典序尽量大。

现在设 A 为先手，你需要求出游戏结束后的 $f$。

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

数据范围：

$1 \le n \le 3\times 10^5$

一个显然的贪心方案，让双方都在最前面填上符合自己利益的字符。

这个贪心是不正确的，因为当 A 最小的字符大于 B 最大的字符时，原有方案会得到较大的答案。

那么怎么办呢？我们可以在这个时候从反向贪心，这样出现问题的那个位置就会填上不大于 B 最大字符的字符。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))

char s[N];
int n,a[N],b[N],f[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1); n = strlen(s + 1);
    for(int i = 1; i <= n; i++) a[i] = s[i] - 'a';
    cin >> (s + 1); n = strlen(s + 1);
    for(int i = 1; i <= n; i++) b[i] = s[i] - 'a';
    sort(a + 1, a + 1 + n, less<int>());
    sort(b + 1, b + 1 + n, greater<int>());
    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; }
        (i & 1) ? (f[i] = a[++x]) : (f[i] = b[++y]);
    }
    x = y = (n >> 1) + 1; if(n & 1) ++x;
    for(int i = n; i > pos; i--) {
        ((pos + n - i + 1) & 1) ? (f[i] = a[--x]) : (f[i] = b[--y]);
    }
    for(int i = 1; i <= n; i++) { cout << char(f[i] + 'a'); } cout << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/120362/solution-cf794c