AT_abc402_c 题解

son_son · 2025-04-19 22:31:40 · 题解

思路

首先可以注意到，每道菜能吃的时间，只跟其中在数组 B 中出现过的配菜能吃的时间相关，也就是这道菜之中最晚能吃那个配菜的时间。

知道题几乎已经解决了。首先将 B 中的配菜开个桶记下来，跑每个菜的每道配菜从而可以知道这道菜能吃的时间。

注意到每道菜能吃的时间是具有单调性的。也就是如果这道菜 t 秒能吃，那么 t+1 秒也能吃。所以将每道菜的最早可吃时间排序一下，每走到一个新的时间点加上其对应的菜的数目就做完啦！

AC code

#include<bits/stdc++.h>
using namespace std;
long long n,m,k[300005],bt[300005],cm[300005];
vector<long long>a[300005];
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%lld",&k[i]);
        for(int j=1;j<=k[i];j++){
            long long _;
            scanf("%lld",&_);
            a[i].push_back(_);
        }
    }
    for(int i=1;i<=n;i++){
        long long _;
        scanf("%lld",&_);
        bt[_]=i;
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<k[i];j++){
            cm[i]=max(cm[i],bt[a[i][j]]);
        }
    }
    sort(cm+1,cm+m+1);
    long long j=1;
    for(int i=1;i<=n;i++){
        while(cm[j]<=i && j<=m)j++;
        printf("%lld\n",j-1);
    }
}