题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4302 ， 可以用线段树，也可以STL中的map,multiset,优先队列中的任何一个解决(可我只会线段树QAQ)。
这道题的解决方法还是比较难想的，我是参考了kuangbin的博客才想到的方法，附链接：http://www.cnblogs.com/kuangbin/archive/2012/08/30/2664289.html
题目解法：
用线段树来维护区间的最大值与最小值，设当前位置为cur，则对于每次询问，就可以求cur左边区间蛋糕位置的最大值与cur右边区间位置的最小值，选择离cur最近的那个位置即可，此时要更新cur，并且删掉该位置的一个蛋糕，并且调整运动的方向。
这道题还有几个注意点：这道题的区间是从0到n的，所以具体解的时候要自己调整 ； 初始化线段树中的最大值与最小值 ； 每个位置的蛋糕不止一个，但是每次吃蛋糕的时候只会吃掉一个，所以要注意线段树更新的时候添加和删除蛋糕的个数(我是用一个cnt数组来存每个位置有几个蛋糕，这样可以避免出错) ；如果两边都没有蛋糕的话就停在当前位置 ；最后就是不要忘了运动的方向问题。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF INT_MAX
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int MOD = 10000007;
const int maxn = 100000 + 5;
const int N = 1000000 + 5;
int Max[maxn << 2] , Min[maxn << 2] , cnt[maxn << 2];
void PushUp(int rt)
{
Max[rt] = max(Max[rt << 1] , Max[rt << 1 | 1]);
Min[rt] = min(Min[rt << 1] , Min[rt << 1 | 1]);
}
void build(int l , int r , int rt)
{
if(l == r) {
cnt[rt] = 0;
Max[rt] = 0;
Min[rt] = INF;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void update(int pos , int x , int l , int r , int rt)
{
if(l == r) {
if(x) { //添加一个
Max[rt] = x;
Min[rt] = x;
cnt[rt]++;
} else { //删除一个
if(cnt[rt] == 1) {
Max[rt] = 0;
Min[rt] = INF;
}
cnt[rt]--;
}
return;
}
int m = (l + r) >> 1;
if(pos > m)
update(pos , x , rson);
else
update(pos , x , lson);
PushUp(rt);
}
int query_max(int L , int R , int l , int r , int rt)
{ //询问[L , R]区间的最大值
if(L <= l && R >= r) {
return Max[rt];
}
int m = (l + r) >> 1;
if(R <= m)
return query_max(L , R , lson);
else if(L > m)
return query_max(L , R , rson);
else
return max(query_max(L , R , lson) , query_max(L , R , rson));
}
int query_min(int L , int R , int l , int r , int rt)
{ //询问[L , R]区间的最小值
if(L <= l && R >= r) {
return Min[rt];
}
int m = (l + r) >> 1;
if(R <= m)
return query_min(L , R , lson);
else if(L > m)
return query_min(L , R , rson);
else
return min(query_min(L , R , lson) , query_min(L , R , rson));
}
void right(int &ans , int &dir , int &cur , int MIN , int n)
{ //向右移动到MIN位置
ans += MIN - cur;
dir = 1;
cur = MIN;
update(MIN , 0 , 1 , n + 1 , 1); //删掉MIN位置一个蛋糕
}
void left(int &ans , int &dir , int &cur , int MAX , int n)
{ //向左移动到MAX位置
ans += cur - MAX;
dir = 0;
cur = MAX;
update(MAX , 0 , 1 , n + 1 , 1); //删掉MAX位置一个蛋糕
}
int main()
{
int T , i , n , m , p , ch;
int ans , cur , dir; //结果 ， 当前位置 ， 运动方向
cin >> T;
for(int k = 1 ; k <= T ; k++)
{
ans = 0;
cur = dir = 1;
scanf("%d %d" , &n , &m);
build(1 , n + 1 , 1);
while(m--) {
scanf("%d" , &ch);
if(!ch) {
scanf("%d" , &p);
update(p + 1 , p + 1 , 1 , n + 1 , 1);
} else {
int MAX = query_max(1 , cur , 1 , n + 1 , 1);
int MIN = query_min(cur , n + 1 , 1 , n + 1 , 1);
if(MAX == 0 && MIN == INF) {
continue;
} else if(MAX != 0 && MIN == INF) {
left(ans , dir , cur , MAX , n);
} else if(MAX == 0 && MIN != INF) {
right(ans , dir , cur , MIN , n);
} else {
if(MIN - cur < cur - MAX) {
right(ans , dir , cur , MIN , n);
} else if(MIN - cur > cur - MAX) {
left(ans , dir , cur , MAX , n);
} else {
if(dir) {
right(ans , dir , cur , MIN , n);
} else {
left(ans , dir , cur , MAX , n);
}
}
}
}
}
printf("Case %d: %d
" , k , ans);
}
return 0;
}
PS：等学了STL就用STL把这个题给解决了