[CF1383A] String Transformation 1 - 貪心

Description

有字符串\(A\)，\(B\)，每次在\(A\)中選取若干個(gè)相同的字母（設(shè)為\(x\)），改成另一個(gè)字母(設(shè)為\(y\))，需要滿足 \(x<y\)，問(wèn)將A改成B的最少操作。

Solution

貪心，每次將所有沒(méi)改過(guò)的最小元素改成他所有目標(biāo)中的最小元素，然后將剩下的加入這個(gè)新元素的目標(biāo)集合中

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

#define int long long

void solve()
{
    string a, b;
    int n;
    cin >> n;
    cin >> a >> b;

    vector<vector<int>> g(20);

    for (int i = 0; i < n; i++)
    {
        int x = a[i] - 'a';
        int y = b[i] - 'a';
        if (x > y)
        {
            cout << -1 << endl;
            return;
        }
        if (x < y)
        {
            g[x].push_back(y);
        }
    }

    int ans = 0;
    for (int i = 0; i < 20; i++)
    {
        sort(g[i].begin(), g[i].end());
        unique(g[i].begin(), g[i].end());
        if (g[i].size())
        {
            int m = g[i][0];
            ++ans;
            for (int j : g[i])
                if (j != m)
                    g[m].push_back(j);
        }
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}