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就是交换次数。求逆序对采用了树状数组,维护原串中的字符下标的优先顺序采用了队列。
代码:
#includeusing 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月01日 23时51分27秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
我的2018总结
2019-04-21
WinRAR存在严重的安全漏洞影响5亿用户
2019-04-21
Dockerfile参考
2019-04-21
吐槽Javascript系列二:数组中的splice和slice方法
2019-04-21
django开发-django和tornado的不同
2019-04-21
行内元素有哪些?块级元素有哪些? 空(void)元素有那些?
2019-04-21
220. Contains Duplicate III
2019-04-21
vue+node全栈移动商城【8】-vant新建注册页面
2019-04-21
JavaScript五十问——对比来说CSS的Grid与FlexBox(下篇)
2019-04-21
枚举的使用示例
2019-04-21
如何导入golang.org的包
2019-04-21
猴子数据让你深刻了解微信富媒体
2019-04-21
浅谈深拷贝和浅拷贝
2019-04-21
区块链技术特点之去中心化特性
2019-04-21
柯里化
2019-04-21
Spring Cloud Gateway 使用 Token 验证
2019-04-21
Spring源码分析:声明式事务梳理
2019-04-21
记一次前端面试试水笔记
2019-04-21
为什么大家觉得前端开发很难做下去?关于我的一些思考
2019-04-21
Quick BI 的模型设计与生成SQL原理剖析
2019-04-21