AT_abc382_c [ABC382C] Kaiten Sushi 题解

lee_0730 · 2024-12-03 22:29:34 · 题解

题目简述：

有 N 个人，第 i 个人的值为 A_i 。同时有 M 个寿司，第 i 个寿司的值为 B_i 。 如果一个人的值小于等于这个寿司的值，这个人就会吃掉它，并且后面的人不会再见到这个寿司。求第 1,2 \dots M 个寿司分别会被谁拿走？

暴力（ 40 pts 左右）：

简单分析，N 个人， M 个寿司，O(NM) 的时间复杂度，简单实惠，如果是有部分分的考试这些分已经够了。

代码：

#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 )，不过无伤大雅）。

代码：

#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;
        }
    }//完成！
}