程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> FZU 1894(單調隊列第一發)

FZU 1894(單調隊列第一發)

編輯:關於C++

題意:參加志願者選拔的同學們排隊接受面試官們的面試。參加面試的同學們按照先來先面試並且先結束的原則接受面試官們的考查。

  輸入 含義 1 C NAME RP_VALUE 名字為NAME的人品值為RP_VALUE的同學加入面試隊伍。(名字長度不大於5,0 <= RP_VALUE <= 1,000,000,000) 2 G 排在面試隊伍最前面的同學面試結束離開考場。 3 Q 主面試官John想知道當前正在接受面試的隊伍中人品最高的值是多少。

思路:直接維護一個單調遞減序列,那麼序列首就是最大值。因為是按照先來先走的規則,所以每一次更新的話把原來的在此位置的那個人捨棄掉。

 

#include
#include
#define maxn 1000000

struct node{
    int x,val;
}q[maxn];

int main()
{
    int t;
    char name[6],na[10],start[12];
    int rp;
    scanf(%d,&t);
    while(t--)
    {
        int i,j,k,head=0,tail=-1,last=0,K=1;
        scanf(%s,start);
        while(scanf(%s,name)!=EOF)
        {
            if(strcmp(name,END)==0) break;
            if(name[0]=='C')
            {
                scanf(%s%d,na,&rp);
                while(tail>=head&&q[tail].val<=rp) tail--;
                node a;
                a.x = K++;
                a.val = rp;
                q[++tail]=a;
            }
            else if(name[0]=='Q')
            {
                while(tail>=head&&q[head].x<=last) head++;
                if(tail>=head) printf(%d
,q[head].val);
                else printf(-1
);
            }
            else last++;
        }
    }
    return 0;
}
 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved