题解：AT_abc174_d [ABC174D] Alter Altar

tangible_love · 2025-09-22 16:51:34 · 题解

思路

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

没有 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 换到最前面去。于是就做完了。

实现

首先读入。

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

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

最后看应该是 R 的位置，就是前 cnt 个里有几个 W，这些就要换掉。

代码

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