第三题:T3交换的次数
标签:逆序数、思维、前缀和
题意:给定一个长度为
n
n
n的
01
01
01序列,
1
1
1和
0
0
0相邻就将
1
1
1调后面去,问最终调换的次数。
(
1
≤
n
≤
300
,
000
1≤n≤300,000
1≤n≤300,000)
题解:很典型的一个逆序数,求每个数后面有多少的比自己小的数,因为
n
n
n比较大,两层循环去求逆序数肯定会超时,这边可以通过归并排序或者树状数组之类的数据结构去查询。但是这个序列中又只有
1
1
1和
0
0
0,那我们可以通过后缀和统计一下
0
0
0的数量,到时候从前往后跑一下每个
1
1
1的位置,统计一下每个
1
1
1的位置后面有多少个
0
0
0的数。
或者反过来想看看每个
0
0
0之前有多少个
1
1
1,直接正着跑一边,对应计数即可。下面给出两种算法的代码
这边注意一个细节,最坏情况 数量可能爆
i
n
t
int
int,得开
l
o
n
g
l
o
n
g
long\ long
long long。
代码 1:
#include <bits/stdc++.h>
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;
}
代码 2:
#include <bits/stdc++.h>
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;
}