题解：AT_abc174_d [ABC174D] Alter Altar

思路

提供一个比较严谨的思路。

没有 WR 这个子串，并且只有 W 和 R，发现最后的答案一定是 RR...RRRWWW...WWW 这个样子。

反证法。如果有 W 在 R 的左边，那它后面一定要是 W，不然就出现了 WR。一直推下去会发现必须全是 W。与一开始的 W 在 R 的左边矛盾，所以所有 R 一定在 W 的左边。

问题变成考虑修改出一段 R 并且后面全是 W。考虑前

i-1

个都是 R 的情况，对于第

i

个而言如果是 R 就不管它，是 W 的话，如果后面还有 R，那直接交换显然是优的，不然直接结束了。

仔细观察上面的过程相当于直接把所有 R 换到最前面去。于是就做完了。

实现

首先读入。

CPP

cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);//这三行是对cin的优化
cin>>n>>s;

然后统计一共有几个 R。记作

cnt

。

最后看应该是 R 的位置，就是前

cnt

个里有几个 W，这些就要换掉。

代码

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,cnt,ans;
string s;
signed main(){
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>s;
	s=" "+s;
	for(int i=1;i<=n;i++) if(s[i]=='R') cnt++;
	for(int i=1;i<=cnt;i++) if(s[i]=='W') ans++;
	cout<<ans;
	return 0;
}

题解：AT_abc174_d [ABC174D] Alter Altar

文章操作

思路

实现

代码

相关推荐

评论

题解：AT_abc174_d [ABC174D] Alter Altar