HDU4302 线段树

　　题目链接：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 = ;

const int maxn =  + ;

const int N =  + ;

int Max[maxn << ] , Min[maxn << ] , cnt[maxn << ];

void PushUp(int rt)

{

    Max[rt] = max(Max[rt << ] , Max[rt <<  | ]);

    Min[rt] = min(Min[rt << ] , Min[rt <<  | ]);

}

void build(int l , int r , int rt)

{

    if(l == r) {

        cnt[rt] = ;

        Max[rt] = ;

        Min[rt] = INF;

        return;

    }

    int m = (l + r) >> ;

    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] == ) {

                Max[rt] = ;

                Min[rt] = INF;

            }

            cnt[rt]--;

        }

        return;

    }

    int m = (l + r) >> ;

    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) >> ;

    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) >> ;

    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 = ;

    cur = MIN;

    update(MIN ,  ,  , n +  , );    //删掉MIN位置一个蛋糕

}

void left(int &ans , int &dir , int &cur , int MAX , int n)

{                    //向左移动到MAX位置

    ans += cur - MAX;

    dir = ;

    cur = MAX;

    update(MAX ,  ,  , n +  , );    //删掉MAX位置一个蛋糕

}

int main()

{

    int T , i , n , m , p , ch;

    int ans , cur , dir;    //结果 ， 当前位置 ， 运动方向

    cin >> T;

    for(int k =  ; k <= T ; k++)

    {

        ans = ;

        cur = dir = ;

        scanf("%d %d" , &n , &m);

        build( , n +  , );

        while(m--) {

            scanf("%d" , &ch);

            if(!ch) {

                scanf("%d" , &p);

                update(p +  , p +  ,  , n +  , );

            } else {

                int MAX = query_max( , cur ,  , n +  , );

                int MIN = query_min(cur , n +  ,  , n +  , );

                if(MAX ==  && MIN == INF) {

                    continue;

                } else if(MAX !=  && MIN == INF) {

                    left(ans , dir , cur , MAX , n);

                } else if(MAX ==  && 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\n" , k , ans);

    }

    return ;

}

　　PS：等学了STL就用STL把这个题给解决了

巴特西

HDU4302 线段树

最新文章

热门文章