POJ 4302 Holedox Eating

POJ 4302 Holedox Eating

Problem Description

Holedox is a small animal which can be considered as one point. It lives in a straight pipe whose length is L. Holedox can only move along the pipe. Cakes may appear anywhere in the pipe, from time to time. When Holedox wants to eat cakes, it always goes to the nearest one and eats it. If there are many pieces of cake in different directions Holedox can choose, Holedox will choose one in the direction which is the direction of its last movement. If there are no cakes present, Holedox just stays where it is.

Input

The input consists of several test cases. The first line of the input contains a single integer T (1 <= T <= 10), the number of test cases, followed by the input data for each test case.The first line of each case contains two integers L,n(1<=L,n<=100000), representing the length of the pipe, and the number of events.
The next n lines, each line describes an event. 0 x(0<=x<=L, x is a integer) represents a piece of cake appears in the x position; 1 represent Holedox wants to eat a cake.
In each case, Holedox always starts off at the position 0.

Output

Output the total distance Holedox will move. Holedox don’t need to return to the position 0.

Sample Input

3
10 8
0 1
0 5
1
0 2
0 0
1
1
1 

10 7
0 1
0 5
1
0 2
0 0
1
1

10 8
0 1
0 1
0 5
1
0 2
0 0
1
1

Sample Output

Case 1: 9
Case 2: 4 

Case 3: 2 

http://blog.csdn.net/watermuch/article/details/12320167
题意：一个小孩吃蛋糕，他的起始点在0位置，现在有m个操作，0 x 代表在x位置出现一个蛋糕；  1 代表小孩要去离他最近的点吃蛋糕，如果与他距离最小的点有两个，则去与他上次走的方向相同的点； 如果没有蛋糕，他就不动。 询问m次操作过后，小孩走了多少距离。
X. TreeSet
https://blog.csdn.net/lwt36/article/details/48446687
分析: 没啥就是一个multiset或者map模拟的水题  有个trick就是 - - 有可能会被呆在原地的多个吃的 隐藏的修改了方向然后就跪了

          数据还是水了 题目里的数据只有一个方向的 如果不判断等于pre也可以过  但是等于nxt的数据是有的

结论: 论仔细思考 然后写出优美代码的重要性!

    while(t--) {
        scanf("%d%d", &n, &q);
        multiset<int> s;
        multiset<int>::iterator iter;
        int cur = 0, dir = 1;
        long long ans = 0;
        while(q--) {
//          printf("q: %d\n", q);
            int op, x; scanf("%d", &op);
            if(op == 0) {
                scanf("%d", &x);
                s.insert(x);
            } else {
                if(s.size() == 0) continue;

                iter = s.lower_bound(cur);
                if(iter == s.end()) x = *(--iter);
                else if(iter == s.begin()) x = *iter;
                else {
                    int r = *iter, l = *(--iter);
                    if(cur - l > r - cur) x = r;
                    else if(cur - l < r - cur) x = l;
                    else x = dir ? r : l;
                }

                if(x > cur) dir = 1;
                else if(x < cur) dir = 0;

                ans += abs(x - cur);
                cur = x;
                s.erase(s.find(x));
            }
        }
        printf("Case %d: %I64d\n", ++kase, ans);
    }
X.
每次保证到达距离当前最近的位置，若两边相同则选择方向不变的那个方向
由于数据较多，不可以直接选择，那样时间复杂度较高O(N*N)，可以用优先级队列降低时间复杂度，当前位置左边的用从大到小排列，右边的从小到大排列，每次移动前比较两个方向的移动距离，左边的肯定与最大的比较，左边的肯定与最小的就比较，于是有了优先级队列的思想，左边大顶堆，右边的小顶堆，总的时间复杂度为O(n*log)，应该可以接受。
https://cloverii.github.io/2015-09-14/hdu-4302-holedox-eating/

不过说实话，用两个pq维护虽然听上去很机智，但是代码比较丑 也可能是我写的不好看吧 - - 感觉 multiset 或者 map 写会更简单

ll solve(void) {

    priority_queue <int> pql;

    priority_queue <int, vector<int>, greater<int> > pqr;

    int n, q, a, b;

    ll ans = 0;

    int pre = 1, now = 0;

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

    while(q--) {

        scanf("%d", &a);

        if(!a) {

            scanf("%d", &b);

            if(b >= now) pqr.push(b);

            else pql.push(b);

        } else {

            int choice = 1, lef = -inf, rig = inf;

            if(pql.size())

                lef = pql.top();

            if(pqr.size())

                rig = pqr.top();

            if(now - lef != rig - now) {

                if(now - lef < rig - now) 

                    choice = -1;

            } else choice = pre;

            if(choice > 0 && rig != inf) {

                pqr.pop();

                ans += rig - now;

                if(rig != now)

                    pre = choice;                

                now = rig;

            } else if(choice < 0 && lef != -inf) {

                pql.pop();

                ans += now - lef;

                pre = choice;

                now = lef;

            }

        }

    }

    return ans;

}

http://blog.csdn.net/watermuch/article/details/8957272
优先队列做法：用两个优先队列维护信息，蛋糕大于他当前所在位置的，用从小到大的优先级；蛋糕小于等于他当前所在位置，用从大到小的优先级。两个队列取出的元素再进行比较

1. struct cmp  
2. {  
3.     bool operator () (int x,int y)  
4.     {  
5.         return x > y;  
6.     }  
7. };  
8.   
9. priority_queue<int , vector<int>, cmp>q; //小到大  
10. priority_queue<int>qq; //大到小  
11. int l,n;  
12. int tt,pos,x=0;  
13. int sum=0,index = 1;  
14.   
15. void Forword() //向前走  
16. {  
17.     int tmp = q.top();  
18.     q.pop();  
19.     sum += tmp - x;  
20.     index = 1;  
21.     x = tmp;  
22.   
23. }  
24. void Back() //向后走  
25. {  
26.     int tmp = qq.top();  
27.     qq.pop();  
28.     sum += x - tmp;  
29.     index = 0;  
30.     x = tmp;  
31.   
32. }  
33.   
34. int main()  
35. {  
36.     int t,Case=1;  
37.     cin >> t;  
38.     while(t--)  
39.     {  
40.         while(!q.empty())  
41.             q.pop();  
42.         while(!qq.empty())  
43.             qq.pop();  
44.         scanf("%d%d",&l,&n);  
45.         x=0;  
46.         sum=0;  
47.         index = 1;  
48.         for(int i=0; i<n; i++)  
49.         {  
50.             scanf("%d",&tt);  
51.             if(!tt)  
52.             {  
53.                 cin >> pos;  
54.                 if(pos <= x)  
55.                     qq.push(pos);  
56.                 else  
57.                     q.push(pos);  
58.             }  
59.             else  
60.             {  
61.                 if(q.empty() && qq.empty())  
62.                     continue;  
63.                 if(q.empty() && ! qq.empty())  
64.                 {  
65.                     Back();  
66.                     continue;  
67.                 }  
68.                 if(qq.empty() && !q.empty())  
69.                 {  
70.                     Forword();  
71.                     continue;  
72.                 }  
73.                 if(!q.empty() && !qq.empty())  
74.                 {  
75.                     int tmp1 = q.top();  
76.                     int tmp2 = qq.top();  
77.                     if(tmp1 - x < x - tmp2 )  
78.                     {  
79.                         Forword();  
80.                     }  
81.                     else if(tmp1 - x > x - tmp2)  
82.                     {  
83.                         Back();  
84.                     }  
85.                     else  
86.                     {  
87.                         if(!index)  
88.                             Back();  
89.                         else  
90.                             Forword();  
91.                     }  
92.   
93.                 }  
94.             }  
95.         }  
96.         printf("Case %d: %d\n",Case++,sum);  
97.     }  
98.     return 0;  
99. }  
100. 
     

X.

每一次，用二分判断，他右边离他最近的蛋糕点，和左边离他最近的蛋糕点。如何判断呢，只需用树状数组维护蛋糕总数，判断小孩当前位置pos 与 mid之间的蛋糕数是否大于等1，是的话可以尝试逼近，否则就远离。

需要注意线段是1 --- L ，而小孩起始点在0，所以有L + 1 个点。

1. int n,m;  
2. int c[MAX];  
3.   
4. int lowbit(int x) {  
5.     return x & (-x);  
6. }  
7.   
8. void update(int x,int va) {  
9.     while(x < n + 2) {  
10.         c[x] += va;  
11.         x += lowbit(x);  
12.     }  
13. }  
14.   
15. int query(int x) {  
16.     int sum = 0;  
17.     while(x > 0) {  
18.         sum += c[x];  
19.         x -= lowbit(x);  
20.     }  
21.     return sum;  
22. }  
23.   
24. int judge(int p,int rp,int lp,int flag) {  
25.     if(rp == -1 && lp == -1) return -1;  
26.     if(rp == -1) return 0;  
27.     if(lp == -1) return 1;  
28.     if(rp - p > p - lp) return 0;  
29.     if(rp - p < p - lp) return 1;  
30.     if(flag == 0) return 0;  
31.     return 1;  
32. }  
33.   
34. int find(int pos,int l,int r,int kind) {  
35.     int mid , des;  
36.     if(kind == 1) des = INF;  
37.     else des = -1;  
38.     while(l <= r) {  
39.         mid = (l + r) >> 1;  
40.         if(kind == 1) {  
41.             if(query(mid) - query(pos - 1) >= 1) {  
42.                 des = min(des,mid);  
43.                 r = mid - 1;  
44.             } else l = mid + 1;  
45.         } else {  
46.             if(query(pos) - query(mid - 1) >= 1) {  
47.                 des = max(des,mid);  
48.                 l = mid + 1;  
49.             } else r = mid - 1;  
50.         }  
51. //        cout << l << ' ' << mid << ' ' << r << endl;  
52.     }  
53.     if(des == INF) return -1;  
54.     return des;  
55. }  
56.   
57. int main() {  
58.     int T;  
59.     cin >> T;  
60.     int ca = 1;  
61.     while(T--) {  
62.         scanf("%d%d",&n,&m);  
63.         memset(c,0,sizeof(c));  
64.         int a,b;  
65.         int pos = 1, flag = 1; //flag 1:right  0: left  
66.         __int64 dis = 0;  
67.         for(int i=0; i<m; i++) {  
68.             scanf("%d",&a);  
69.             if(a == 1) {  
70.                 int rpos = find(pos,pos,n+1,1);  
71.                 int lpos = find(pos,1,pos,0);  
72.                 int dir = judge(pos,rpos,lpos,flag);  
73.                 if(dir == -1) continue;  
74.                 if(dir == 1) {  
75.                     dis += rpos - pos;  
76.                     pos = rpos;  
77.                     flag = 1;  
78.                 } else {  
79.                     dis += pos - lpos;  
80.                     pos = lpos;  
81.                     flag = 0;  
82.                 }  
83.                 update(pos,-1);  
84.             } else {  
85.                 scanf("%d",&b);  
86.                 update(b+1,1);  
87.             }  
88.         }  
89.         printf("Case %d: %d\n",ca ++,dis);  
90.     }  
91.     return 0;  
92. }