学好数理化，走遍天下都不怕

DTOJ1039 吃蛋糕

发表于 更新于 分类于

题目

题目描述

小明是个蛋糕爱好者，连做梦都想着吃蛋糕——然后，他真的作了这样一个梦：
现在他在一个长为$L$的管道里，坐标从$0\sim L$，开始时，他在$0$这个位置
一些事件依次发生，比如说，小明想吃蛋糕，或者是蛋糕出现了
如果小明想吃蛋糕，那么他会挑选最近的那个蛋糕吃掉
如果左右两个蛋糕的距离是一样的，那么他就选择跟吃上一个蛋糕同样移动方向上的
否则，他就选那个距离较近的蛋糕
要是一个蛋糕都没出现，那么他就呆在原地不动
蛋糕会随机出现在管道的任何位置
请你统计一下，小明一共走了多少距离

输入格式

输入第一行是两个整数$L,N$
$L$是管道的长度，$N$是事件的数量$(1\leqslant L,N\leqslant 100000)$
接下来$N$行，首先是一个整数，表示事件的种类：如果是$1$，表示小明要吃蛋糕，后面什么也没有；如果是$0$，表示有个蛋糕出现了，后面跟一个整数，表示蛋糕出现的位置$(0\leqslant x\leqslant L)$

输出格式

输出一个整数，表示小明一共走了多少距离

样例

样例输入1

1
2
3
4
5
6
7
8
9
10 8
0 1
0 5
1
0 2
0 0
1
1
1

样例输出2

1
9

样例输入2

1
2
3
4
5
6
7
8
10 7
0 1
0 5
1
0 2
0 0
1
1

样例输出2

1
4

数据范围与提示

对于$50\%$的数据， $L,N\leqslant 5000$
对于$100\%$的数据， $L,N\leqslant 100000$

题解

直接两个优先队列，分别存小明左边和右边的蛋糕的位置（一个从小到大，一个从大到小），吃蛋糕时就直接弹出，并且把小明的位置换到蛋糕的位置，更新答案；加蛋糕时就看蛋糕在小明的那一边，直接加就好了
当然，你也可以用一些平衡树什么之类的，但是那样比较麻烦
附上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int> qx;
priority_queue<int,vector<int>,greater<int> > qd;
int l,n,a,ans,flag;
int main()
{
    scanf("%d%d",&l,&n);
    for(int i=1,op,x;i<=n;i++){
        scanf("%d",&op);
        if(!op){
            scanf("%d",&x);
            if(x<a) qx.push(x);
            else qd.push(x);
        }
        else{
            if(!qd.empty()&&!qx.empty()){
                if(a-qx.top()==qd.top()-a){
                    if(!flag) ans+=a-qx.top(),flag=0,a=qx.top(),qx.pop();
                    else ans+=qd.top()-a,flag=1,a=qd.top(),qd.pop();
                    continue;
                }
                if(a-qx.top()<qd.top()-a) ans+=a-qx.top(),flag=0,a=qx.top(),qx.pop();
                else ans+=qd.top()-a,flag=1,a=qd.top(),qd.pop();
                continue;
            }
            if(qd.empty()&&!qx.empty()){ans+=a-qx.top(),flag=0,a=qx.top(),qx.pop();continue;}
            if(!qd.empty()&&qx.empty()){ans+=qd.top()-a,flag=1,a=qd.top(),qd.pop();continue;}
        }
    }
    printf("%d",ans);
}