Juggler
题目:http://acm.hdu.edu.cn/showproblem.php?pid=4262
题意:有个数字圆环。三种操作:逆时针转一个,顺时针转一个,丢掉手中的那个的同时顺时针的数字到你的手里。每个操作都花费一秒。告诉你要求的出圈顺序,求最小花费时间。注:开始在手中的球为1.
题解:假设当前要移除的珠子为i,我们会发现无论左移还是右移都会得到同一个序列,即移去某个数字对后面的数字序列无影响,所以每次只需单独考虑左移和右移的长度,取最小累加即可。
代码:
#include<cstdio> #include<cstring> #include<list> #include<algorithm> using namespace std; #define MAX 100005 #define ab(x) ((x)>0?(x):-(x)) int summ[MAX<<2];//区间内有几个数字 int pos[MAX];//询问顺序 void push_up(int idx) { summ[idx]=summ[idx<<1]+summ[idx<<1|1]; return; } void build(int l,int r,int idx) { if(l==r) { summ[idx]=1; return; } int mid=(l+r)>>1; build(l,mid,idx<<1); build(mid+1,r,idx<<1|1); push_up(idx); } void update(int p,int l,int r,int idx) { if(l==r) { summ[idx]=0; return; } int mid=(l+r)>>1; if(p<=mid) update(p,l,mid,idx<<1); else update(p,mid+1,r,idx<<1|1); push_up(idx); } long long query(int a,int b,int l,int r,int idx) { if(a<=l&&r<=b) { return summ[idx]; } int mid=(l+r)>>1; long long ans=0; if(a<=mid) ans+=query(a,b,l,mid,idx<<1); if(mid<b) ans+=query(a,b,mid+1,r,idx<<1|1); return ans; } int main() { int n,a,c,d; for(; scanf("%d",&n),n;) { long long sumt=0,cnt; build(1,n,1); for(int i=1; i<=n; ++i) { scanf("%d",&a); pos[a]=i; } a=1; for(int i=1; i<=n; ++i) { sumt++; if(a!=pos[i]) { if(a==1) c=0; else c=query(1,a-1,1,n,1); if(pos[i]==1) d=0; else d=query(1,pos[i]-1,1,n,1); cnt=ab(c-d); sumt+=min(cnt,n-i+1-cnt); } update(pos[i],1,n,1); a=pos[i]; } printf("%I64d\n",sumt); } return 0; }