本文主要是介绍TOJ 4354 HDU 4262 Juggler / 树状数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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 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.
输出
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.
样例输入
3
3
2
1
0
样例输出
5
提示
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 <stdio.h>
#include <string.h>
const int MAX = 100010;
int n;
int a[MAX];
int map[MAX];int min(int x,int y)
{return x < y ? x : y;
}
int lowbit(int t)
{ return t & ( t ^ ( t - 1 ) );
}
int sum(int end)
{ int sum = 0; while(end > 0) { sum += a[end]; end -= lowbit(end); } return sum;
}
void plus(int pos , int num)
{ while(pos <= n) {a[pos] += num; pos += lowbit(pos); }
} int main()
{int i,x,s;while(scanf("%d",&n),n){memset(a,0,sizeof(a));for(i = 1; i <= n; i++){scanf("%d",&x);map[x] = i;}int k = 1;__int64 cnt = n;for(i = 1;i < n; i++){if(i == 1)s = map[i] - 1;else if(k < map[i])s = map[i] - k - (sum(map[i]) - sum(k)) - 1;elses = k - map[i] - (sum(k - 1) - sum(map[i] - 1));plus(map[i],1);cnt += min(s,n - i - s + 1);k = map[i]; }printf("%I64d\n",cnt);}return 0;
}
这篇关于TOJ 4354 HDU 4262 Juggler / 树状数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!