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=;
int n, x, num;
int cnt[maxn], tree[maxn], pos[][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=; for(;x;x-=x&-x) sum+=tree[x]; return sum;}
int main()
{
scanf("%s", s+); n=strlen(s+);
for(int i=;i<=n;i++) cnt[x=s[i]-'a']++, pos[x][++pos[x][]]=i, tree[i]=i&-i;
for(int i=;i<;i++) if(cnt[i]&) num++;
if(num>) return puts("-1"), ;
for(int i=;i<=n;i++)
if(!v[i])
{
int x=s[i]-'a', nxt=pos[x][pos[x][]--];
if(i==nxt) ans+=(query(n)-query(i))>>;
else ans+=query(n)-query(nxt);
add(i, -); add(nxt, -); v[i]=v[nxt]=;
}
printf("%lld\n", ans);
}
上一篇:Git生成ssh密钥指定文件


下一篇:Spark基础脚本入门实践3:Pair RDD开发