awoo‘s Favorite Problem(优先队列)

原题链接

题目描述

给你两个字符串s和t，长度都是n。两个字符串中的每个字符都是’a’， ‘b’或’c’。

在一个操作中，您可以执行以下操作之一:

选择s中出现的“ab”，将其替换为“ba”;

选择s中出现的“bc”，并将其替换为“cb”。

你可以执行任意数量的移动(可能是零)。 你能改变字符串s让它等于字符串t吗?

输入样例

5
3
cab
cab
1
a
b
6
abbabc
bbaacb
10
bcaabababc
cbbababaac
2
ba
ab

输出样例

YES
NO
YES
YES
NO

---

算法

(贪心 + 优先队列 + 模拟)

贪心策略：通过优先队列记录每个字母的下标，每次如果有可换的字母对则取最近的下标观察是否可以交换，没有则直接弹出该字母。

C++ 代码

时间复杂度 $O(nlogn)$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll a[N],s[N];

void solve()
{
    int n;
    cin >> n;
    string s,t;
    cin >> s >> t; 
    vector<int> v1(3,0),v2(3,0);
    for (int i = 0;i < n;i ++ ) v1[s[i] - 'a'] ++;
    for (int i = 0;i < n;i ++ ) v2[t[i] - 'a'] ++;

    if (v1 == v2) {
        priority_queue<int,vector<int>,greater<int>>a,b,c;
        for(int i = 0;i < n;i ++ ) {
            if(s[i] == 'a') a.push(i);
            if(s[i] == 'b') b.push(i);
            if(s[i] == 'c') c.push(i);
        }
        for (int i = 0;i < n;i ++ ) {
            if (s[i] == t[i]) {
                if (s[i] == 'a') a.pop();
                else if (s[i] == 'b') b.pop();
                else c.pop();
            }else {
                if (s[i] == 'a' && t[i] == 'b') {
                    if (!b.empty() && (c.empty() || b.top() < c.top())) {
                        int index = b.top();
                        b.pop();
                        swap(s[i],s[index]);
                        a.pop();
                        a.push(index);
                        continue;
                    }
                }else if (s[i] == 'b' && t[i] == 'c') {
                    if (!c.empty() && (a.empty() || c.top() < a.top())) {
                        int index = c.top();
                        c.pop();
                        swap(s[i],s[index]);
                        b.pop();
                        b.push(index);
                        continue;
                    }
                }
                puts("NO");
                return;
            }
        } 
        puts("YES");
    }else puts("NO");
}
int main()
{
    int t;
    cin >> t;
    while (t -- ) solve();
    return 0;
}