codeforces-1430E(树状数组+逆序对)
发布日期:2022-03-30 18:18:17 浏览次数:26 分类:博客文章

本文共 1045 字,大约阅读时间需要 3 分钟。

codeforces1430E-String Reversal

题目链接:

题目描述:

给定一个字符串(abcd),将该字符串转换为它的反转字符串(dcba),只可以交换相邻的字符,问一共需要交换多少次

思路:

把字符串倒置,反转字符串的每个字符在原串中一定是优先采取最近的字符移动过来,很显然这种相邻交换字符的方式符合逆序对的计算,比如对于字符串"aabcd"的下标原本是(1,2,3,4,5),反转后的字符串"dcbaa"对应的下标就应该是(5,4,3,1,2),求出的逆序对数9就是交换次数。求逆序对采用了树状数组,维护原串中的字符下标的优先顺序采用了队列。

代码:

#include
using namespace std;using ll = long long;const ll N = 2e5+5;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();ll C[N],n;int lowbit(int x){return x&(-x);}void update(int i,int v){ while(i<=n){ C[i]+=v; i+=lowbit(i); }}int getsum(int i){ ll ans = 0; while(i){ ans+=C[i]; i-=lowbit(i); } return ans;}int main() { cin>>n; string s; cin>>s; queue
q[100]; for(int i = 0; i < n; i++){ q[s[i]-'a'].push(i+1); } reverse(s.begin(),s.end()); ll ans = 0; for(int i = 0; i < n; i++){ int id = q[s[i]-'a'].front(); update(id,1); q[s[i]-'a'].pop(); ans+=i+1-getsum(id); } cout<
<

转载地址:https://www.cnblogs.com/cloudplankroader/p/13867019.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:C++中图片重命名
下一篇:codeforces-1461D(二分)

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月01日 23时51分27秒