UESTC 1063 秋实大哥与妹纸 二叉堆(小根堆)

#include   
#include   
using namespace std;  
const int maxn = 125001;  
  
int heap[maxn],  sz = 1;  
  
inline void up(int i){
    int x = heap[i];
    for(int j = i >> 1; j >= 1; j >>= 1) {
        if(heap[j] > x){
            heap[i] = heap[j];
            i = j;
        } else {
            break;
        }
    }
    heap[i] = x;
}
inline void down(int i){
    int x = heap[i];
    for(int j = i << 1; j <= sz; j <<= 1){
        j += j < sz && heap[j] > heap[j+1];
        if(heap[j] < x){
            heap[i] = heap[j];
            i = j;
        } else {
            break;
        }
    }
    heap[i] = x;
}
inline void push(int v){
    heap[++sz] = v;
    up(sz);
}
inline void pop(){
    swap(heap[1], heap[sz]);
    sz--;
    down(1);
}
inline int top(){
    return heap[1];
}
inline bool _empty(){
    return sz == 0;
}
inline int _size(){
    return sz;
} 
  
int main()  
{  
    int n, a;  
    scanf("%d", &n);  
    for(int i = 0; i < n/2 +1; i++){  
        scanf("%d", &a);push(a);  
    }  
    for(int i = n/2 +1; i < n; i++){  
        scanf("%d", &a);  
        push(a);pop();  
    }  
    pop();  
    if(n % 2 ==1) printf("%.1f", (double)heap[1]);  
    else{  
        a = top();pop();  
        printf("%.1f", (double)a/2+(double)top()/2);  
    }  
    return 0;  
}

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx