2015
05-23

Juggler

As part of my magical juggling act, I am currently juggling a number of objects in a circular path with one hand. However, as my rather elaborate act ends, I wish to drop all of the objects in a specific order, in a minimal amount of time. On each move, I can either rotate all of the objects counterclockwise by one, clockwise by one, or drop the object currently in my hand. If I drop the object currently in my hand, the next object (clockwise) will fall into my hand. What’s the minimum number of moves it takes to drop all of the balls I’m juggling?

There will be several test cases in the input. Each test case begins with an integer n, (1≤n≤100,000) on its own line, indicating the total number of balls begin juggled. Each of the next n lines consists of a single integer, ki (1≤kin), which describes a single ball: i is the position of the ball starting clockwise from the juggler’s hand, and ki is the order in which the ball should be dropped. The set of numbers {k1, k2, …, kn} is guaranteed to be a permutation of the numbers 1..n. The input will terminate with a line containing a single 0.

There will be several test cases in the input. Each test case begins with an integer n, (1≤n≤100,000) on its own line, indicating the total number of balls begin juggled. Each of the next n lines consists of a single integer, ki (1≤kin), which describes a single ball: i is the position of the ball starting clockwise from the juggler’s hand, and ki is the order in which the ball should be dropped. The set of numbers {k1, k2, …, kn} is guaranteed to be a permutation of the numbers 1..n. The input will terminate with a line containing a single 0.

3
3
2
1
0

5
Hint
Explanation of the sample input: The first ball is in the juggler’s hand and should be dropped third; the second ball is immediately clockwise from the first ball and
should be dropped second; the third ball is immediately clockwise from the second ball and should be dropped last.


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define lson u<<1
#define rson u<<1|1
#define MAXN 100005

int map[MAXN];

struct Node{
int lef,rig;
int sum;
}T[MAXN<<2];

void PushUp(int u){
T[u].sum=T[lson].sum+T[rson].sum;
}

void Build(int u,int l,int r){
T[u].lef=l;
T[u].rig=r;
if(l==r){T[u].sum=1;return;}
int mid=(l+r)>>1;
Build(lson,l,mid);
Build(rson,mid+1,r);
PushUp(u);
}

void Update(int u,int pos,int val){
if(T[u].lef==T[u].rig){T[u].sum=val;return;}
if(pos<=T[lson].rig)Update(lson,pos,val);
else Update(rson,pos,val);
PushUp(u);
}

int Query(int u,int l,int r){
if(l<=T[u].lef&&T[u].rig<=r)return T[u].sum;
if(r<=T[lson].rig)return Query(lson,l,r);
if(l>=T[rson].lef)return Query(rson,l,r);
return Query(lson,l,T[lson].rig)+Query(rson,T[rson].lef,r);

}

int main(){
int n;
while(scanf("%d",&n)&&n){
int tmp;
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
map[tmp]=i;
}
Build(1,1,n);

int cur=1;
__int64 ans=n;

for(int i=1;i<n;i++){
if(i==1)tmp=Query(1,cur,map[i])-1;
else if(map[i]>cur)tmp=Query(1,cur+1,map[i])-1;
else tmp=Query(1,map[i],cur-1);
ans+=min(tmp,n-i+1-tmp);
Update(1,map[i],0);
cur=map[i];
}
printf("%I64d\n",ans);
}
return 0;
}