[CF 522C] Chicken or Fish?

作法：

以下把不確定拿了哪樣的人稱做「隨便」。首先可以發現，只有第一個難過的人有意義（記這個時間點為 T），代表在這之前已經有其中一種被拿完了，而後面難過的人我們都可以假設他一開始選的是已經被拿完的那樣。所以在第一個難過的人之後的人拿到的菜裡面，一定都是在 T 時還沒被拿完的菜，也就是「在 T 時被拿完的菜」的候選人只有「從 T 開始一直到結束都沒有人拿到他」的菜，並且還必須滿足 T 時累積的隨便的個數要>=他當時剩下的個數。因此對於一道菜，我們想判斷他有沒有可能最後被拿完，第一種可能就是他在第一個人難過前就已經被拿完了，另外一種可能則是在有人難過之後。前者已經討論過了，而如果是後者的話，累積到最後一刻的隨便的數量必須要先全部丟給「 T 時被拿完的那道菜」，剩下的再去拿當前這道，如果可以拿完就代表可以。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
 
int a[maxn],b[maxn] ;
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int m,k ; scanf("%d%d",&m,&k) ;
        for(int i=1;i<=k;i++) scanf("%d",&a[i]) ;
 
        int x=-1 , y=0 ;
        while(--m)
        {
            int t,r ; scanf("%d%d",&t,&r) ;
            if(r==1 && x==-1)
            {
                x=y ;
                for(int i=1;i<=k;i++) b[i]=a[i] ;
            }
            if(t) a[t]-- ;
            else y++ ;
        }
 
        int mi=maxn ;
        for(int i=1;i<=k;i++)
            if(a[i]==b[i]) mi=min(mi,b[i]) ;
        for(int i=1;i<=k;i++)
        {
            if(x==-1 && y>=a[i]) printf("Y") ;
            else if(x==-1) printf("N") ;
            else if(x>=b[i] && a[i]==b[i]) printf("Y") ;
            else if(y-mi>=a[i]) printf("Y") ;
            else printf("N") ;
        }
        printf("\n") ;
    }
}