题解 P1198 【[JSOI2008]最大数】

wuliang1 · 2016-02-10 20:03:00 · 题解

    #include "stdio.h"  
    #include "string.h"  
    int f[200010];  
    int main()  
    {  
        int t,now,m,d,x,i;  
        char ch[2];  
        while (scanf("%d%d",&m,&d)!=EOF)  
        {  
            t=0;  
            now=0;  
            while (m--)  
            {  
                scanf("%s%d",ch,&x);  
                if (ch[0]=='A')  
                {  
                    f[++now]=(x+t)%d;  
                    for (i=now-1;i>=1;i--)  
                    if (f[i]<f[now]) f[i]=f[now];  
                    else break;  
                }  
                else  
                    printf("%d\n",t=f[now-x+1]);  
            }  
        }  
        return 0;  
    }  

如果一个节点在队列中既没有时间优势（早点入队）也没有值优势（值更大），那么显然无论在怎样的情况下都不会被选为最大值。

既然它只在末尾选，那么自然可以满足以上的条件。