当前位置:网站首页>awoo‘s Favorite Problem(优先队列)
awoo‘s Favorite Problem(优先队列)
2022-07-01 21:45:00 【山中一扶苏】
原题链接
题目描述
给你两个字符串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 ( 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;
}
边栏推荐
- Business visualization - make your flowchart'run'up
- 收到一封CTO来信,邀约面试机器学习工程师
- 从MLPerf谈起:如何引领AI加速器的下一波浪潮
- GenICam GenTL 标准 ver1.5(4)第五章 采集引擎
- Using closures to switch toggle by clicking a button
- 比较版本号[双指针截取自己想要的字串]
- Relationship and difference between enterprise architecture and project management
- pytest合集(2)— pytest運行方式
- Classify boost libraries by function
- IDA动态调试apk
猜你喜欢
[live broadcast review] the first 8 live broadcasts of battle code Pioneer have come to a perfect end. Please look forward to the next one!
基于三维GIS的不动产管理应用
flink sql-client 使用 对照并熟悉官方文档
微软、哥伦比亚大学|GODEL:目标导向对话的大规模预训练
黑马程序员-软件测试--06阶段2-linux和数据库-01-08第一章-linux操作系统阶段内容说明,linux命令基本格式以及常见形式的说明,操作系统的常见的分类,查看命令帮助信息方法,
比较版本号[双指针截取自己想要的字串]
指标陷阱:IT领导者易犯的七个KPI错误
Manually implement function isinstanceof (child, parent)
Training on the device with MIT | 256Kb memory
JS how to get a list of elements in a collection object
随机推荐
高攀不起的希尔排序,直接插入排序
Copy ‘XXXX‘ to effectively final temp variable
Getting started with the lockust series
二叉树的基本操作
Chapter 9 Yunji datacanvas company has been ranked top 3 in China's machine learning platform market
企业架构与项目管理的关联和区别
月入1W+的自媒体达人都会用到的运营工具
详解JMM
Mask wearing detection method based on yolov5
【直播回顾】战码先锋首期8节直播完美落幕,下期敬请期待!
linux下清理系统缓存并释放内存
Difference and use between require and import
辅音和声母的区别?(声母与辅音的区别)
记录一次spark on yarn 任务报错 Operation category READ is not supported in state standby
Interview question: what is the difference between MySQL's Union all and union, and how many join methods MySQL has (Alibaba interview question) [easy to understand]
Recent public ancestor offline practice (tarjan)
In the past 100 years, only 6 products have been approved, which is the "adjuvant" behind the vaccine competition
LIS (longest ascending subsequence) problem that can be understood [easy to understand]
Qtreeview+qabstractitemmodel custom model: the third of a series of tutorials [easy to understand]
Classify boost libraries by function