思路:
纯粹是堆的建立和push、pop操作,这次没有使用priority_queue,自己编写了堆。
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho有一个糖果盒子,每过一段时间小Ho都会将新买来的糖果放进去,同时他也会不断的从其中挑选出最大的糖果出来吃掉,但是寻找最大的糖果不是一件非常简单的事情,所以小Ho希望能够用计算机来他帮忙计算这个问题!
输入
每个测试点(输入文件)有且仅有一组测试数据。
在一组测试数据中:
第1行为1个整数N,表示需要处理的事件数目。
接下来的M行,每行描述一个事件,且事件类型由该行的第一个字符表示,如果为’A’,表示小Ho将一粒糖果放进了盒子,且接下来为一个整数W,表示这颗糖果的重量;如果为’T’,表示小Ho需要知道当前盒子中最重的糖果的重量是多少,在知道这个值之后,小Ho会将这颗糖果从盒子中取出并吃掉。
对于100%的数据,满足1<=N<=10^5, 1<=w<=10^5。<>
对于100%的数据,满足没有2颗糖果的重量是相同的,最开始的时候小Ho的糖果盒子是空的,且每次小Ho想要取出一颗糖果的时候盒子里一定至少有一颗糖果。
输出
在一组测试数据中:
对于每个类型为’T’的时间,输出1个整数W_MAX,表示在这一时刻,盒子中最重的糖果的重量。
- 样例输入
-
5 A 77751 A 1329 A 26239 A 80317 T
- 样例输出
-
80317
AC代码:
#include<stdio.h> int arr[100002] = { 0 }; int size = 0; int pop() { if (size == 0) return 0; int result = arr[0];//获取栈顶元素 int x = arr[--size];//把队尾元素提到0号位置 int i = 0; int a = i * 2 + 1;//左孩子 int b = i * 2 + 2;//右孩子 while (a<size) { if (b<size&&arr[a]<arr[b]) a = b;//右孩子比左孩子大 if (x<arr[a])//孩子的值比父亲大,提上来 arr[i] = arr[a]; else//父亲的值比孩子大,停止操作 break; i = a; a = i * 2 + 1; b = a + 1; } arr[i] = x; return result; } void push(int x) { int i = size++; int p = (i - 1) / 2;//父亲节点 while (x>arr[p]) {//孩子节点的值比父亲的值大 arr[i] = arr[p]; i = p; if (i == 0) break; p = (i - 1) / 2; } arr[i] = x; } int main() { int n; scanf("%d", &n); while (n--) { char c[10]; scanf("%s", c); if (*c == 'A') { int x; scanf("%d", &x); push(x); } else printf("%d\n", pop()); } return 0; }