板刷贪心总结

题单

AT_agc029_a [AGC029A] Irreversible operation

有 $ N $ 个奥赛罗棋子排成一列。每个棋子的状态由长度为 $ N $ 的字符串 $ S $ 表示，当 $ S_i=$B 时，从左数第 $ i $ 个棋子的表面为黑色；当 $ S_i=$W 时，从左数第 $ i $ 个棋子的表面为白色。

现在考虑执行以下操作：

• 选择一个满足 $ 1 \leq i < N $ 的索引 $ i $，要求从左数第 $ i $ 个棋子表面为黑色且第 $ i+1 $ 个棋子表面为白色。将这两个棋子同时翻转，即第 $ i $ 个棋子变为白色，第 $ i+1 $ 个棋子变为黑色。

求最多能执行多少次该操作。

思路：

为什么我自己没有做出来

其实这道题就是求逆序对的个数

那就从后往前遍历，统计遇到的 W 个数，遇到 B 就将答案加上 W 的个数

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
//不开long long 见祖宗
int n, w, ans;
string s;
signed main()
{cin >> s;s = " " + s;n = s.size() - 1;for(int i = n; i >= 1; i --){if(s[i] == 'W'){w ++;}if(s[i] == 'B'){ans += w;}}cout << ans << endl;
}