题解 P4032 【[Code+#2]火锅盛宴】
钱逸凡
2020-10-30 15:25:24
# 解题思路
这题一共三个询问，我们可以先从最简单的第三个询问开始分析
## 第三个询问
我们可以用线段树（树状数组）来维护所有已经熟的食物，**每次询问的时间复杂度为O（logn）**
## 第一个询问
由于我们在做第三问时建立一颗线段树（树状数组），所以我们这里可以直接用线段树来解决这一问：
若整个区间的和为0，则没有食物。
若有食物，则：
用二分来找出有值但最小的点（左右端点相同的区间），该点就是所求的食物编号，每次询问的时间复杂度为O（（logn）^2），然后将该点减一,复杂度O(1)，所以，**这步总的复杂度为O（（logn）^2）**
## 第二个询问
我们给每一个食物建一个队列（因为同一种食物煮熟花的时间相同，所以越晚入队，煮熟的时间就越晚），每次询问时如果队列为空，则没有食物，如果队列最前面的元素小于当前时间，则成功，否则，则用队列最前面的元素减去当前时间，即为还需等待的时间，复杂度O(1)
## 一二问相互影响问题
由于拿走食物对一二问都有影响，所以我们在第一问删除时，要把用于第二问的队列元素出队，同样，在第二问删除时，要把用于第一三问的线段树更新，**所以第二问的复杂度变为O(logn)**
## 加入新的食物所需的操作
每次加入新的食物，我们将该食物煮熟的时间加入该食物的队列中，**注意：不要更新线段树，只有食物煮熟时才更新线段树**
## 在每一步之前的操作
根据现在的时间，把所有已经煮熟的食物加入对应的队列和线段树中
# 注意事项
注意清空数据，防止影响到下一组数据！！！
# 代码实现
```
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
using namespace std;
int n;
const int mx=101010;
inline int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
queue<int>food[mx];
int q_num;//询问总数
int cost[mx];//每种食物需要的时间
#define lowbit(i) i&-i
int tree[mx];
void change(int pos,int k){//pos位置+k
while(pos<=n){
tree[pos]+=k;
pos+=lowbit(pos);
}
}
int query(int pos){//查询到pos为止有多少个食物
int ans=0;
while(pos>=1){
ans+=tree[pos];
pos-=lowbit(pos);
}
return ans;
}
struct FOOD{//食物
int t;//煮熟时间
int pos;//食物编号
};
struct cmp1{
bool operator () (const FOOD &a,const FOOD &b)const{
return a.t>b.t;//按照结束时间从小到大排
}
};
priority_queue<FOOD,vector<FOOD>,cmp1>f1;//食物
void query_1(){//第一个问题：拿出编号最小的食物
if(!query(n)){//没有任何食物
printf("Yazid is angry.\n");
return;
}
int l=1,r=n,mid=(l+r)>>1;
while(l<r){
if(query(mid)-query(l-1))r=mid;
else l=mid+1;
mid=(l+r)>>1;
}
printf("%d\n",mid);
food[mid].pop();//食物出堆
change(mid,-1);
return;
}
void query_2(int pos,int t){//第二问，pos食物是否有熟的，如果没有，最快熟的还要多久
if(food[pos].empty()){//没有该食物
printf("YJQQQAQ is angry.\n");
return;
}
int tp=food[pos].front();
if(tp<=t){//熟了
printf("Succeeded!\n");
food[pos].pop();//从堆中删除该食物
change(pos,-1);//从树状数组中删除该食物
return;
}
else{
printf("%d\n",tp-t);
return;
}
}
void query_3(int l,int r){//第三个问题：查询[l,r]之间有多少个食物
printf("%d\n",query(r)-query(l-1));
return;
}
int main(){
int T=Read();
while(T--){
q_num=0;
n=Read();
for(int i=1;i<=n;++i)cost[i]=Read();
int num=Read();
for(int i=1;i<=num;++i){
int t=Read();
int opt=Read();
if(!f1.empty()){
FOOD tp=f1.top();
while(tp.t<=t){
f1.pop();
change(tp.pos,1);
if(f1.empty())break;
tp=f1.top();
}
}
if(opt==0){
int pos=Read();
FOOD a;
a.pos=pos;
a.t=t+cost[pos];
f1.push(a);
food[pos].push(t+cost[pos]);
}
else if(opt==1){
query_1();
}
else if(opt==2){
int pos=Read();
query_2(pos,t);
}
else{
int l=Read(),r=Read();
query_3(l,r);
}
}
//清除数据，为下一组数据做准备
memset(tree,0,sizeof(tree));
while(!f1.empty())f1.pop();
for(int i=1;i<=n;i++)while(!food[i].empty())food[i].pop();//清空队列
}
return 0;
}
```
因为太懒所以用了优先队列和树状数组，你们可以用手写堆和线段树