[贪心] [字典序] CF254C Anagram

_Cheems · 2024-02-27 14:08:30 · 题解

我们用桶 buc 记录每个字符在 S 中的个数减去在 T 中的个数，我们称 buc<0 的字符为 1 类字符，buc>0 的字符为 2 类字符。

显然我们需要且仅需要将 2 类字符换成 1 类字符，于是第一问的答案为 2 类字符的 buc 之和。

然后是第二问。字典序最小，考虑贪心。我们从左往右遍历 S 并维护 buc，然后分类讨论。

• * 如果能找到当前最小的满足 $c<S_i$ 的一类字符 $c$，则将 $S_i$ 换成 $c$。 * 如果不能，则判断当前字符是否必须操作，如果是则找到当前最小的一类字符 $c$，并将 $S_i$ 换成 $c$。否则不需操作。

正确性显然，复杂度 O(n)，带个 26 的常数。

最后有个坑，就是这道题需要 freopen。。。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, P = 26;
int n, buc[P], ans, s[N], mp[P];
char a[N], b[N];

signed main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1);
    for(int i = 1; i <= n; ++i) ++buc[a[i] - 'A'], --buc[b[i] - 'A'];
    for(int i = n; i >= 1; --i) s[i] = s[mp[a[i] - 'A']] + 1, mp[a[i] - 'A'] = i;
    for(int i = 1; i <= n; ++i){
        if(buc[a[i] - 'A'] > 0){
            int id = -1, id2 = -1;
            for(int j = P; ~j; --j)
                if(buc[j] < 0){
                    id2 = j;
                    if(j < a[i] - 'A') id = j;
                }
            if(id == -1){
                if(s[i] <= buc[a[i] - 'A']) {
                    ++buc[id2], --buc[a[i] - 'A'], ++ans;
                    a[i] = char('A' + id2);
                }
            }
            else{
                ++buc[id], --buc[a[i] - 'A'], ++ans;
                a[i] = char('A' + id);
            }
        }
    }
    printf("%d\n%s", ans, a + 1);
    return 0;
}