题意:就是排队问题,有插入,删除,询问操作,加到队列里的人有一个权值,删除就是删除当前队列里的第一个人,询问就是当前队列里的人的最大权值,插入就是插入一个人到队尾。
解题思路:我是来复习一下单调队列的,以前学过一点,但是没理解,所以不多说了。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std ; const int maxn = 1111111 ; struct Dqueue { int pos[maxn] , val[maxn] ; int star , tail ; void init () { star = 1 , tail = 0 ; } void push ( int id , int v ) { while ( tail >= star && val[tail] < v ) tail -- ; val[++tail] = v ; pos[tail] = id ; } bool empty () { return star > tail ; } int front () { return val[star] ; } int front_p () { return pos[star] ; } void pop () { if ( star <= tail ) star ++ ; } } q ; char s[111] ; char op[111] ; int main () { int t ; scanf ( "%d" , &t ) ; while ( t -- ) { q.init () ; scanf ( "%s" , s ) ; int cnt = 0 ; int id = 0 ; while ( scanf ( "%s" , op ) != EOF ) { if ( op[0] == 'E' ) break ; if ( op[0] == 'G' ) { cnt ++ ; if ( cnt == q.front_p () ) q.pop () ; } if ( op[0] == 'C' ) { int a ; id ++ ; scanf ( "%s%d" , s , &a ) ; q.push ( id , a ) ; } if ( op[0] == 'Q' ) { if ( !q.empty () ) printf ( "%d\n" , q.front () ) ; else puts ( "-1" ) ; } } } return 0 ; }