ZX1019 逆序对字母
大约 1 分钟
ZX1019 逆序对字母
【算法】 前缀和、逆序对
【C++】 字符串、前缀和计数、long long
【难度】 普及−
一、题目简述
给定一个全小写字母字符串 (),求其中逆序对字母的数量。逆序对字母: 且 (ASCII 比较)。
二、解题思路
暴力两重循环 会超时()。需要用前缀和计数。
遍历字符串,维护 cnt[26] 表示当前已遍历过的各字母出现次数。对于当前字符 ,它前面所有大于 的字母都能和 形成逆序对。
即:ans += sum(cnt[c+1 .. 25])
每次遍历完当前字符后 cnt[c]++。
手动模拟 "bbba":
- i=0 ('b'): 大于'b'的字母没有,cnt['b']=1
- i=1 ('b'): 同样没有,cnt['b']=2
- i=2 ('b'): 没有,cnt['b']=3
- i=3 ('a'): 大于'a'的有'b'(3个),ans+=3
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int cnt[26]; // 各字母出现次数
int main() {
string s;
cin >> s;
long long ans = 0;
for (char c : s) {
int idx = c - 'a';
// 统计前面所有大于当前字符的数量
for (int j = idx + 1; j < 26; j++) {
ans += cnt[j];
}
cnt[idx]++;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间:,,可以过。
- 空间:,只需 26 大小的计数数组。
五、优化
可进一步用树状数组维护前缀和,将每次查询优化到 ,但本题 26 个字母足够小,直接循环即可。
