锐客网

  1. 首页 > 睿知 > it技术 > >

AtCoder Regular Contest 088 E - Papple Sort（树状数组+结论）

IT知识树状数组AtCodercontest

识字粗堪供赋役，不须辛苦慕公卿。这篇文章主要讲述AtCoder Regular Contest 088 E - Papple Sort（树状数组+结论）相关的知识，希望能为你提供帮助。
结论：每次把字符丢到最外面最优，用树状数组统计答案，把字符放到最外边后可以当成消失了，直接在树状数组上删掉就好。
【AtCoder Regular Contest 088 E - Papple Sort（树状数组+结论）】感性理解是把字符丢到中间会增加其他字符的移动次数，但是丢到外面不会，所以是正确的。

AtCoder Regular Contest 088 E - Papple Sort（树状数组+结论）

文章图片
AtCoder Regular Contest 088 E - Papple Sort（树状数组+结论）

文章图片
#include< iostream> #include< cstring> #include< cstdlib> #include< cstdio> #define ll long long using namespace std; const int maxn=500010; int n, x, num; int cnt[maxn], tree[maxn], pos[26][maxn]; ll ans; char s[maxn]; bool v[maxn]; inline void add(int x, int delta){for(; x< =n; x+=x& -x) tree[x]+=delta; } inline int query(int x){int sum=0; for(; x; x-=x& -x) sum+=tree[x]; return sum; } int main() { scanf("%s", s+1); n=strlen(s+1); for(int i=1; i< =n; i++) cnt[x=s[i]-‘a‘]++, pos[x][++pos[x][0]]=i, tree[i]=i& -i; for(int i=0; i< 26; i++) if(cnt[i]& 1) num++; if(num> 1) return puts("-1"), 0; for(int i=1; i< =n; i++) if(!v[i]) { int x=s[i]-‘a‘, nxt=pos[x][pos[x][0]--]; if(i==nxt) ans+=(query(n)-query(i))> > 1; else ans+=query(n)-query(nxt); add(i, -1); add(nxt, -1); v[i]=v[nxt]=1; } printf("%lld\n", ans); }

View Code 

    推荐阅读


    上一篇：Android开发学习-四大组件

    下一篇：Android查缺补漏--ContentProvider的使用