[CF1383A] String Transformation 1 - 贪心

[CF1383A] String Transformation 1 - 贪心

Description

有字符串\(A\)，\(B\)，每次在\(A\)中选取若干个相同的字母（设为\(x\)），改成另一个字母(设为\(y\))，需要满足 \(x<y\)，问将A改成B的最少操作。

Solution

贪心，每次将所有没改过的最小元素改成他所有目标中的最小元素，然后将剩下的加入这个新元素的目标集合中

#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();
    }
}

[CF1383A] String Transformation 1 - 贪心

原文：https://www.cnblogs.com/mollnn/p/14504053.html