当前位置:网站首页>Awoo's favorite problem (priority queue)
Awoo's favorite problem (priority queue)
2022-07-01 22:39:00 【A Fusu in the mountains】
Original link
Title Description
Here are two strings s and t, All the lengths are n. Each character in both strings is ’a’, ‘b’ or ’c’.
In one operation , You can do one of the following :
choice s What happened in “ab”, Replace it with “ba”;
choice s What happened in “bc”, And replace it with “cb”.
You can perform any number of moves ( It could be zero ). You can change the string s Make it equal to string t Do you ?
sample input
5
3
cab
cab
1
a
b
6
abbabc
bbaacb
10
bcaabababc
cbbababaac
2
ba
ab
sample output
YES
NO
YES
YES
NO
Algorithm
( greedy + Priority queue + simulation )
Greedy strategy : Record the subscript of each letter through the priority queue , Each time if there are interchangeable letter pairs, take the nearest subscript and observe whether they can be exchanged , If not, the letter will pop up directly .
C++ Code
Time complexity O ( n l o g n ) O(nlogn) 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;
}
边栏推荐
- 详解LockSupport的使用
- awoo‘s Favorite Problem(优先队列)
- Qtreeview+qabstractitemmodel custom model: the third of a series of tutorials [easy to understand]
- Slope compensation
- Smart micro mm32 multi-channel adc-dma configuration
- YOLOv5.5 调用本地摄像头
- Slope compensation
- Slope compensation
- Mask wearing detection method based on yolov5
- 【juc学习之路第9天】屏障衍生工具
猜你喜欢
随机推荐
JVM有哪些类加载机制?
Training on the device with MIT | 256Kb memory
The correct way to set the bypass route
Mysql——》索引存储模型推演
【juc学习之路第9天】屏障衍生工具
分享一个一年经历两次裁员的程序员的一些感触
Learning notes on futuretask source code of concurrent programming series
隐藏用户的创建和使用
Copy ‘XXXX‘ to effectively final temp variable
Indicator trap: seven KPI mistakes that it leaders are prone to make
The second anniversary of the three winged bird: the wings are getting richer and the take-off is just around the corner
Yyds dry goods inventory # solve the real problem of famous enterprises: egg twisting machine
linux下清理系统缓存并释放内存
91.(cesium篇)cesium火箭发射模拟
MySQL中对于索引的理解
Mysql——》Innodb存储引擎的索引
【MySQL】索引的创建、查看和删除
互联网的智算架构设计
并发编程系列之FutureTask源码学习笔记
MySQL的视图练习题