warm up的第六题，当时就看出来是线段树了，只是因为一些细节问题，没有A掉，做题目的时候心浮气躁。看来要走的路还很长。
这题目有三种动作让我们选择 1：顺时针移动一格 2：逆时针移动一格 3：把第一个球丢掉。
问我们最少多少个动作把球从小到大丢掉。这题的数据量很大，我想到了查询从当前要丢掉的球的位置顺时针到第一个球和逆时针到第一个球所在的位置上还剩余多少个球，来求出最少的动作。（这里的第一个球是上一次动作丢掉的球的位置，模拟的时候要注意这里的细节，要仔细，每次丢掉一个球顺时针位置的下一个球补上，因此在求丢掉第i个球最少要多少个动作的时候，顺时针方向求出球的个数后还要+1，而逆时针方向求出的球的个数就是动作个数，这里就是此题关键，其他的部分就是线段树的单点更新）。因为一百万个数，每次都要查询和删除，所以选择线段树。
Juggler
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 204 Accepted Submission(s): 80
Problem Description
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?
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?
Input
There will be several test cases in the input. Each test case begins with an integern, (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≤ki≤n), which describes a single ball: i is the position of the ball starting clockwise from the juggler’s hand, andki 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.
of a single integer,ki (1≤ki≤n), which describes a single ball: i is the position of the ball starting clockwise from the juggler’s hand, andki 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.
Output
For each test case, output a single integer on its own line, indicating the minimum number of moves I need to drop all of the balls in the desired order. Output no extra spaces, and do not separate answers with blank lines. All possible
inputs yield answers which will fit in a signed 64-bit integer.
inputs yield answers which will fit in a signed 64-bit integer.
Sample Input
3 3 2 1 0
Sample Output
5HintExplanation 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<algorithm>
using namespace std;
#define MAXN 200100
#define lson l,m,root<<1
#define rson m+1,r,root<<1|1
int node[MAXN<<2],n;
int m[MAXN]; //记录编号为i的球所在的位置
void push_up(int root)
{
node[root]=node[root<<1]+node[root<<1|1];
}
void build(int l,int r,int root)
{
if(l==r)
{
int temp;
node[root]=1;
scanf("%d",&temp);
m[temp]=l;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
push_up(root);
}
void update(int p,int l,int r,int root)
{
if(l==r)
{
node[root]=0;
return ;
}
int m=(l+r)>>1;
if(p<=m)
update(p,lson);
else
update(p,rson);
push_up(root);
}
int query(int L,int R,int l,int r,int root)
{
if(L<=l && R>=r)
return node[root];
int m=(l+r)>>1;
int ret=0;
if(L<=m)
ret+=query(L,R,lson);
if(R>m)
ret+=query(L,R,rson);
return ret;
}
void solve()
{
long long ans=0; //此处要注意使用long long 或者__int64
int temp,tt,tag;
build(1,n,1);
tag=m[1],tt=tag; //tag当前要丢的球的位置， tt前一次丢掉的球的位置（我们假设的第一个球所在的位置）
ans=min(query(1,tag,1,n,1),query(tag,n,1,n,1)+1); //第一个球特殊处理 ，以为编号为1的球要丢的时候我们假设的第一个球的位置上的球任然存在
update(tt,1,n,1);
for(int i=2;i<=n;i++)
{
//从循环开始tt所在就没有球存在了，因此如果求顺时针动作还要+1，因为真正的第一个球在tt顺时针的下一个有球的位置
tag=m[i];
if(tag>=tt)
temp=min(query(tt,tag,1,n,1),query(tag,n,1,n,1)+query(1,tt,1,n,1)+1);
else
temp=min(query(tag,tt,1,n,1)+1,query(1,tag,1,n,1)+query(tt,n,1,n,1));
update(tag,1,n,1);
ans+=temp;
tt=tag;
}
cout<<ans<<endl;
}
int main()
{
while(scanf("%d",&n)!=EOF && n)
solve();
return 0;
}