HiHo一下 堆 Week28

HiHo

描述

小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

思路

简单的堆

代码

#include<iostream>
using namespace std;
#define MAX 100005
int heap[MAX];
int amount = 1;
void insert(int x){
    int p = amount;
    heap[amount++] = x;
    while((heap[p>>1]<x)&&(p>>1>=1)){
        heap[p] = heap[p>>1];
        p = p>>1;
    }
    heap[p] = x;
}
void down(int p){
    if((p<<1)>amount) return;
    if(heap[p<<1]>heap[p<<1|1]){
        if(heap[p<<1]<heap[p]) return;
            else {
                int t = heap[p];
                heap[p] = heap[p<<1];
                heap[p<<1] = t;
                p = p <<1;
                if((p<<1)<amount) down(p);
            }
    }else{
        if(heap[p<<1|1]<heap[p]) return;
            else {
                int t = heap[p];
                heap[p] = heap[p<<1|1];
                heap[p<<1|1] = t;
                p = p <<1|1;
                if((p<<1)<amount) down(p);
            }
    }
}
void pop(){
    cout <<heap[1]<<endl;
    heap[1] = heap[--amount];
    int p = 1;
    down(p);
}
int main(){
    int n,w;
    char a;
    cin >> n;
    while(n--){
        cin >> a;
        if(a=='A') {
            cin >> w;
            insert(w);
        }
        if(a=='T') pop();
    }
    return 0;
}

//堆优化的Prim
#include<iostream>
using namespace std;
#define MAXN 100004
#define MAXM 1000005
struct ed{
    int to;
    int weight;
    int next;
};
struct edge{
    int x;
    int y;
    int weight;
};
int header[MAXN];
ed tree[MAXM];
edge heap[MAXM];
bool flag[MAXN];
int edgeAmount=1;
void addEdge(int x,int y,int w){
    if(header[x]==0)
        tree[edgeAmount].next = -1;
        else
        tree[edgeAmount].next = header[x];
        tree[edgeAmount].to = y;
        tree[edgeAmount].weight = w;
        header[x] = edgeAmount++;
}
void insert(int x,int y,int weight){
    int p = edgeAmount++;
    heap[p].x = x;
    heap[p].y = y;
    heap[p].weight = weight;
    edge temp = heap[p];
    while((heap[p>>1].weight > temp.weight)&&(p>>1 >=1)){
        heap[p] = heap[p>>1];
        p = p>>1;
    }
    heap[p] = temp;
}
void down(int p){
    int bc=p;
    if(p<<1 > edgeAmount) return ;
    if(heap[p<<1].weight < heap[p<<1|1].weight) 
        bc = p<<1;
    else
        bc = p<<1|1;
    if(heap[bc].weight < heap[p].weight){
        edge tt = heap[p];
        heap[p] = heap[bc];
        heap[bc] = tt;
        down(bc);
    }
}
int pop(){
    int val = heap[1].weight;
    heap[1] = heap[--edgeAmount];
    down(1);
    return val;
}
int main(){
    int n,m,x,y,w;
    scanf("%d%d",&n,&m);
    for(int i =1;i<=n;i++)  header[i] = 0;
    for(int i =1;i<=n;i++)  flag[i] = false;
    while(m--){
        scanf("%d%d%d",&x,&y,&w);
        addEdge(x,y,w);
        addEdge(y,x,w);
    }
    int sum =0;
    flag[1] = true;
    int p =1;
    int s = header[p];
    edgeAmount = 1;
    for(int i=1;i<n;){
        while(tree[s].next!=-1){
            if(!flag[tree[s].to]) insert(p,tree[s].to,tree[s].weight);
            s = tree[s].next;
        }
        while(((flag[heap[1].x])xor(flag[heap[1].y]))==0) pop();
        if(flag[heap[1].x]) {
                flag[heap[1].y] = true;
                p = heap[1].y;
                }else {
                flag[heap[1].x] = true;
                p = heap[1].x;
                }
        s = header[p];
        sum +=pop();
        i++;
    }
    cout << sum;
    return 0;
}