上海计算机学会 2024年4月月赛 丙组T3 交换的次数

第三题：T3交换的次数

标签：逆序数、思维、前缀和
题意：给定一个长度为$n$的$01$序列，$1$和$0$相邻就将$1$调后面去，问最终调换的次数。
（$1\le n\le 300,000$）
题解：很典型的一个逆序数，求每个数后面有多少的比自己小的数，因为$n$比较大，两层循环去求逆序数肯定会超时，这边可以通过归并排序或者树状数组之类的数据结构去查询。但是这个序列中又只有$1$和$0$，那我们可以通过后缀和统计一下$0$的数量，到时候从前往后跑一下每个$1$的位置，统计一下每个$1$的位置后面有多少个$0$的数。
或者反过来想看看每个$0$之前有多少个$1$，直接正着跑一边，对应计数即可。下面给出两种算法的代码
这边注意一个细节，最坏情况 数量可能爆$int$，得开$longlong$。
代码 1：

#include 
using namespace std;

string s;
int suf[300005]; // 后缀0的数量

int main() {
    cin >> s;
    int n = s.size();
    long long ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        suf[i] = suf[i + 1];
        if (s[i] == '0') suf[i]++;
    }
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') ans += suf[i + 1];
    }
    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码 2：

#include 
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    long long ans = 0, cnt = 0; // cnt: 前缀1的数量
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') cnt++;
        else ans += cnt;
    }
    cout << ans << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15