回転寿司

· · 题解

题目大意

题目描述

一群孩子吃寿司，寿司是一个一个端上来的，每一个寿司的好吃度为 a_i，坐在前面的孩子可以优先吃到寿司，一道寿司也只能被一个孩子吃掉。

但吃到寿司需要满足以下条件:

  1. 这个孩子还没吃过寿司。
  2. 这个寿司是这个孩子吃过最好吃的寿司（注意，此人之前吃的寿司好吃度小于此寿司而不是小等于）。

若所有人都不满足条件，这个寿司就不会被吃。

输入格式

第一行输入 N,M，表示孩子的数量，寿司的数量。

第二行输入 N 个数，第 i 个数表示这个寿司的好吃度 a_i。

输出格式

输出 M 个数，第 i 个数 j 表示第 i 个寿司会被第 j 个孩子吃掉（不会被吃则输出 -1）。输出的数用回车隔开。

解答

#1 暴力

就纯模拟就好了，只能拿部分分。

复杂度为 O(nm)。

#include<bits/stdc++.h>
using namespace std;
int n,m,sz[100010];
bool k=false;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)   sz[i]=-1;
    int a,zx=0xfffffff;
    for(int i=1;i<=m;i++){
        cin>>a;
        for(int j=1;j<=n;j++){
            if(k==true&&a<=zx){
                cout<<-1<<endl;
                break;
            }
            if(sz[j]<a){
                sz[j]=a;
                zx=min(sz[j],zx);
                cout<<j<<endl;
                if(j==n)    k=true;//如果最后一个人也吃到寿司说明所有人都吃过了。
                break;
            }
        }
    }
    return 0;
}

#2 正解

依然是数组模拟，但是对于每一次添加进行二分查找，确定该寿司应该被哪个小孩吃掉。由于如果一个寿司同时满足两个孩子的需求，那么它一定会被更前面的孩子吃掉，所以这个数组一定是单调递减的，故解法正确。

时间复杂度为 O(m \log n)。

AC 代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,sz[100010]={0},cnt=0,a;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a;
        int l=1,h=cnt,mid,ans=cnt+1;
        while(l<=h){
            mid=(l+h)>>1;
            if(sz[mid]<a){
                ans=mid;
                h=mid-1;            
            }
            else    l=mid+1;
        }
        if(ans==cnt+1){
            if(cnt<n){
                sz[++cnt]=a;
                cout<<cnt<<endl;
            }   
            else    cout<<-1<<endl; 
        }   
        else{
            sz[ans]=a;
            cout<<ans<<endl;
        }
    }
    return 0;
}

update：2023.6.14，感谢用户 @User_Unauthorized 指出我的错误。