AT_abc382_c [ABC382C] Kaiten Sushi 题解

# 题目简述：
有 $N$ 个人，第 $i$ 个人的值为 $A_i$ 。同时有 $M$ 个寿司，第 $i$ 个寿司的值为 $B_i$ 。
如果一个人的值小于等于这个寿司的值，这个人就会吃掉它，并且后面的人不会再见到这个寿司。求第 $1,2 \dots M$ 个寿司分别会被谁拿走？
# 暴力（ $40$ pts 左右）：
简单分析，$N$ 个人， $M$ 个寿司，$O(NM)$ 的时间复杂度，简单实惠，如果是有部分分的考试这些分已经够了。
## 代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
queue<int>q;
struct node{
	int s,id;//美食值与编号
};
vector<node>v;
int n,m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int mins=INT_MAX;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		v.push_back({x,i+1});
		mins=min(mins,x);
	}//输入，求最小值
	for(int i=0;i<m;i++){
		int x;
		cin>>x;
		bool flag=false;
		if(x<mins){//特判
			cout<<-1<<endl;
			continue;
		}
		for(auto j:v){//遍历美食值
			if(j.s<=x){
				cout<<j.id<<endl;
				flag=true;
				break;
			}
		}
		if(!flag){//不满足条件
			cout<<-1<<endl;
		}
	}
}
```

# 正片  $100$ pts 分析
本题看似是一道**双指针**或**二分**大题，实际上看到 $N$ 的范围，我们可以使用**桶**来**预处理**每一个人的美食值区间，时间复杂度为 $O(\max(N,M))$（没错，就是这么小，本代码由于使用 **map**，会导致实际复杂度为 $O(N \log M )$，不过无伤大雅）。
## 代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
map<int,int> xcs;//由于本题数据量，可以简化成一维数组
int lyt[300005];
int n,m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	memset(lyt,-1,sizeof(lyt));
	int mins=INT_MAX;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		lyt[x]=x;
		if(xcs[x]==0){
			xcs[x]=i+1;
		}
		xcs[x]=min(xcs[x],i+1);//特判，如果美食值相同，按编号决定
	}
	xcs[-1]=1000000;
	int cnt=-1;
	for(int i=0;i<=300000;i++){//预处理食用区间，类似于桶
		if(lyt[i]>xcs){//判断美食值
			if(xcs[cnt]>xcs[lyt[i]]){//美食值不同，判断编号
				cnt=lyt[i];
			}
		}
		lyt[i]=cnt;
	}
	for(int i=0;i<m;i++){//最后的输入
		int x;
		cin>>x;
		if(lyt[x]==-1){
			cout<<-1<<endl;
			continue;
		}else{
			cout<<xcs[lyt[x]]<<endl;
		}
	}//完成！
}
```

正在渲染内容...