思路

首先可以注意到，每道菜能吃的时间，只跟其中在数组

B

中出现过的配菜能吃的时间相关，也就是这道菜之中最晚能吃那个配菜的时间。

知道题几乎已经解决了。首先将

B

中的配菜开个桶记下来，跑每个菜的每道配菜从而可以知道这道菜能吃的时间。

注意到每道菜能吃的时间是具有单调性的。也就是如果这道菜

t

秒能吃，那么

t+1

秒也能吃。所以将每道菜的最早可吃时间排序一下，每走到一个新的时间点加上其对应的菜的数目就做完啦！

AC code

CPP

#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);
    }
}

AT_abc402_c 题解

文章操作

思路

AC code

相关推荐

评论

AT_abc402_c 题解