题解：AT_abc382_c [ABC382C] Kaiten Sushi

· · 题解

题目翻译

有 N 个编号从 1 到 N 的人光顾一家传送带寿司店。第 i 个人的美食级别是 A_i 。

现在， M 块寿司将被放在传送带上。第 j 个寿司的美味程度是 B_j 。每块寿司都会按照这个顺序从 1, 2, \dots, N 人面前经过。当美味程度不低于自己美食水平的寿司从面前经过时，每个人都会拿起并吃掉这个寿司；否则，他们什么也不会做。 i 拿起并吃掉的寿司将不再从 j\ (j > i) 面前经过。

对于每个 M 个寿司，确定谁吃了这个寿司，或者是否没人吃。

题目分析

感觉这题甚至比第四题难。

我的第一反应是从每个人的角度考虑，查找他们会吃的第一个寿司，但是每个寿司只能被吃掉一次，而处理这个就会很头疼。

但是，如果你是一个寿司，你要找到一个人把你吃掉这是在干什么啊，这样就好想多了，因为一个人可以把多个寿司吃掉，没有找到一个人但是他不吃的问题。

于是这道题就迎刃而解了：对于每一个寿司，查找第一个可以把他吃掉的人，就好了。

现在还有一个问题，我们要找到第一个美食级别小于等于当前寿司美味程度的人，即：第一个小于等于 A_i 的 B_j。

但是直接这么找就会超时，但是 B 数组又是乱序的，怎么办呢？

只要对 B 数组求一个前缀最小值数组 P 就可以解决了，这时，如果 P_{mid} \ge A_i，则 P_{mid - 1} \ge A_i，P_{mid-2} \ge A_i，\dots。这样就保证数组是单调递减的，在上面二分就行了。

code

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,m,a[N],b[N],p[N];
int main(){
    cin>>n>>m;
    p[0]=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p[i]=min(p[i-1],a[i]);
    }
    for(int i=1;i<=m;i++)cin>>b[i];
    for(int i=1;i<=m;i++){//寻找第一个小于等于a[i]的b[j] 
        int l=1,r=n,ans=-1;
        while(l<=r){
            int mid=l+r>>1;
            if(p[mid]<=b[i]){
                ans=mid;
                r=mid-1;
            }else l=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}