嘘~ 正在从服务器偷取页面 . . .

CF794C Naming Company 题解

发布日期: 2023-05-18

更新日期: 2023-05-18

文章字数: 594

CF794C Naming Company 题解

题意：

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

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

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

在自己的字符串中选出一个字符 \(x\)。

将 \(f\) 中的一个 ? 替换为 \(x\)。

将 \(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;
}