题目
题目描述
小明是个蛋糕爱好者，连做梦都想着吃蛋糕——然后，他真的作了这样一个梦：
现在他在一个长为$L$的管道里，坐标从$0\sim L$，开始时，他在$0$这个位置
一些事件依次发生，比如说，小明想吃蛋糕，或者是蛋糕出现了
如果小明想吃蛋糕，那么他会挑选最近的那个蛋糕吃掉
如果左右两个蛋糕的距离是一样的，那么他就选择跟吃上一个蛋糕同样移动方向上的
否则，他就选那个距离较近的蛋糕
要是一个蛋糕都没出现，那么他就呆在原地不动
蛋糕会随机出现在管道的任何位置
请你统计一下，小明一共走了多少距离
输入格式
输入第一行是两个整数$L,N$
$L$是管道的长度，$N$是事件的数量$(1\leqslant L,N\leqslant 100000)$
接下来$N$行，首先是一个整数，表示事件的种类：如果是$1$，表示小明要吃蛋糕，后面什么也没有；如果是$0$，表示有个蛋糕出现了，后面跟一个整数，表示蛋糕出现的位置$(0\leqslant x\leqslant L)$
输出格式
输出一个整数，表示小明一共走了多少距离
样例
样例输入1
10 8
0 1
0 5
1
0 2
0 0
1
1
1样例输出2
9样例输入2
10 7
0 1
0 5
1
0 2
0 0
1
1样例输出2
4数据范围与提示
对于$50%$的数据， $L,N\leqslant 5000$
对于$100%$的数据， $L,N\leqslant 100000$
题解
直接两个优先队列，分别存小明左边和右边的蛋糕的位置（一个从小到大，一个从大到小），吃蛋糕时就直接弹出，并且把小明的位置换到蛋糕的位置，更新答案；加蛋糕时就看蛋糕在小明的那一边，直接加就好了
当然，你也可以用一些平衡树什么之类的，但是那样比较麻烦
附上代码：
#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);
}喜欢的话，给博主赏一杯冰阔乐吧~
 |
|
|
