题目大意
有一个圆形管道，里面有N个球，给定N个球的出圈顺序，最初的时候手的位置是在第一个球的位置，如果一个球的位置刚好是手所在的位置，那么它可以被取出，要求你按照给定的出圈顺序，依次取出N个球，在旋转到目标小球的时候，可以向左旋转，也可以向右旋转，每移动一个单位位置，需要一个单位的花费，要求你计算出最少的花费是多少
题解
如果读懂题目了，那么就很好做了，当时模拟的比赛的时候看了好久题目都没有看懂题，o(╯□╰)o。。。对于每一个位置，用1来表示有球，0来表示没求，用线段树来维护前缀和即可，每次查找手所在位置之前有多少个球，然后查找目标小球的位置之前有多少个球，这两个操作都是求前缀和，两个值的差的绝对值就是它们两之间的一个距离d，假设当前处理的是第i个球，那么另外一个距离等于：n-i+1-d。选择两者中的小者。然后进行删除操作（单点更新）
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define MAXN 100005 #define lson l,m,s<<1 #define rson m+1,r,s<<1|1 int sumv[MAXN<<2],pos[MAXN]; void PushUp(int s) { sumv[s]=sumv[s<<1]+sumv[s<<1|1]; } void build(int l,int r,int s) { if(l==r) { sumv[s]=1; return; } int m=(l+r)>>1; build(lson); build(rson); PushUp(s); } void update(int p,int l,int r,int s) { sumv[s]--; if(l==r) return; int m=(l+r)>>1; if(p<=m) update(p,lson); else update(p,rson); } int query(int ql,int qr,int l,int r,int s) { if(ql<=l&&r<=qr) return sumv[s]; int m=(l+r)>>1,ans=0; if(ql<=m) ans+=query(ql,qr,lson); if(qr>m) ans+=query(ql,qr,rson); return ans; } int main(void) { int n,p,a,b,d; while(scanf("%d",&n)!=EOF&&n) { __int64 sum=0; build(1,n,1); for(int i=1; i<=n; i++) { scanf("%d",&p); pos[p]=i; } p=1; for(int i=1; i<=n; i++) { a=0; b=0; if(p-1) a=query(1,p-1,1,n,1); if(pos[i]-1) b=query(1,pos[i]-1,1,n,1); d=abs(a-b); sum+=min(d+1,n-i+2-d); update(pos[i],1,n,1); p=pos[i]; } printf("%I64d\n",sum); } return 0; }
上述方法耗时1156ms,由于题目要求的操作就是查询前缀和以及单点修改，因此可以用树状数组来做，空间消耗和时间消耗都要比用线段树小，耗时只需要390ms
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define MAXN 100005 int c[MAXN],pos[MAXN]; int n; int lowbit(int x) { return x&-x; } void add(int x,int d) { while(x<=MAXN) { c[x]+=d; x+=lowbit(x); } } int sum(int x) { int ret=0; while(x>0) { ret+=c[x]; x-=lowbit(x); } return ret; } int main(void) { int a,b,d,p; while(scanf("%d",&n)!=EOF&&n) { __int64 ans=0; memset(c,0,sizeof(c)); for(int i=1; i<=n; i++) { scanf("%d",&p); pos[p]=i; add(i,1); } int p=1; for(int i=1; i<=n; i++) { a=sum(p-1); b=sum(pos[i]-1); d=abs(a-b); ans+=min(d+1,n-i+2-d); add(pos[i],-1); p=pos[i]; } printf("%I64d\n",ans); } }