TIOJ 1155 4.經濟編碼 [93全國賽(prob 4)]

68011    poao899    1155    Accepted    12K    75MS    G++    0.96K    2010-03-03 22:41:27                 .




噢哈好久沒寫TIOJ了XD

單純Heap這樣

是說 Heap又長得跟之前不一樣了XD

#include<stdio.h>
#define MAX 100010
struct heap{
    double ar[MAX];
    int rear;
    inline void change(int n,int m){
        double t=ar[n];
        ar[n]=ar[m];
        ar[m]=t;
    }
    void upset(int n){
        if(n<2 || n>=rear)return;
        int t=n/2;
        if(ar[t]>ar[n]){
            change(t,n);
            upset(t);
        }
    }
    void downset(int n){
        if(n<1 || n>=rear)return;
        int t=n*2;
        for(int i=0;i<2;i++)
            if(t+i<rear&&ar[n]>ar[t+i]){
                change(t+i,n);
                downset(t+i);
            }
    }
    inline void push(double a){
        ar[rear]=a;
        upset(rear++);
    }
    inline double pop(){
        if(rear==1)return 0;
        double x=ar[1];
        change(1,--rear);
        downset(1);
        return x;
    }
}h;
int n;
char buffer[100];
double total,t;
int main(){
    gets(buffer);
    sscanf(buffer,"%d",&n);
    h.rear=1;
    while(n--){
        gets(buffer);
        sscanf(buffer,"%*c %lf",&t);
        h.push(t);
    }
    for(;;){
        t=h.pop()+h.pop();
        if(h.rear==1)break;
        total+=t;
        h.push(t);
    }
    printf("%.2lf\n",total+t);
    //main();
}