本文主要是介绍FZU 1894 (双端队列),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Problem 1894 志愿者选拔
Accept: 1166 Submit: 3683
Time Limit: 1500 mSec Memory Limit : 32768 KB
Problem Description
Input
输入 | 含义 | |
1 | C NAME RP_VALUE | 名字为NAME的人品值为RP_VALUE的同学加入面试队伍。(名字长度不大于5,0 <= RP_VALUE <= 1,000,000,000) |
2 | G | 排在面试队伍最前面的同学面试结束离开考场。 |
3 | Q | 主面试官John想知道当前正在接受面试的队伍中人品最高的值是多少。 |
Output
Sample Input
2STARTC Tiny 1000000000C Lina 0QGQENDSTARTQC ccQ 200C cxw 100QGQC wzc 500QEND
Sample Output
10000000000-1200100500
Hint
数据较大建议使用scanf,printf 不推荐使用STLSource
福州大学第七届程序设计竞赛题意:一个队列,有入队出队查询操作。查询的时候输出队列中最大值。
思路:单调队列。
代码:
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;typedef pair<int, int> pi;
deque<pi>q;const int N = 15;
int num, head, rear, t;
char start[N], quit[N];int main() {scanf("%d", &t);while (t --) {scanf("%s", start);head = 0; rear = 0;while (!q.empty())q.pop_front();while (scanf("%s", quit) && strcmp(quit, "END") != 0) {if (quit[0] == 'C') {scanf("%s%d", start, &num);while (!q.empty() && q.back().first < num) {q.pop_back();}q.push_back(make_pair(num, rear));rear ++;}else if (quit[0] == 'G') {if (q.front().second == head)q.pop_front();head ++;}else {if (!q.empty())printf("%d\n", q.front().first);elseprintf("-1\n");}}}return 0;
}
这篇关于FZU 1894 (双端队列)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!