TIOJ 1529 邪惡的魔人姜姜 [Greedy]

poao899    15676K    6995MS    G++     1.37K     2010-03-27 13:12:37                                  .




說Greedy應該沒有捏到人吧(小聲

是說讓我爆炸的測資是

2
3.0 5.0
4.0 7.0

我會輸出50.000   應該很明顯問題在哪裡吧XDD

正確輸出是0.000



反正就是維持一個Heap

不過還是不習慣用STL...

小心浮點數誤差(?


//**************************************

#include<stdio.h>
#include<algorithm>
int n,top,allpow;
double pre_t,tored;
double hp;
int inline cmp(double a,double b){
    double d=a-b;
    if(d>10e-7)return -1;
    else if(d<-10e-7)return 1;
    return 0;
}
double min(double a,double b){
    if(cmp(a,b)==1)return a;
    return b;
}
struct loli{
    double w,t;
    bool operator<(const loli &b)const{
        return cmp(t,b.t)==1 || !cmp(t,b.t)&&cmp(w,b.w)==-1;
    }
    void get(){
        scanf("%lf%lf",&w,&t);
    }
}l[500020];
struct ele{
    double w,red;
    bool operator<(const ele &b)const{
        return cmp(w,b.w)==1;
    }
}heap[500020];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        l[i].get();
    std::sort(l,l+n);
    for(int i=0;i<n;i++){
        heap[top].w=l[i].w;
        heap[top++].red=0;
        std::push_heap(heap,heap+top);
        tored=pre_t+l[i].w-l[i].t;
        if(cmp(tored,0.0)==1)tored=0;
        while(cmp(tored,0.0)==-1){
            if(cmp(heap[0].w-heap[0].red , tored)==-1){
                heap[0].red+=tored;
                tored=0;
            }else{
                allpow++;
                tored-=(heap[0].w-heap[0].red);
                heap[0].red=heap[0].w=0;
                std::pop_heap(heap,heap+top);top--;
            }
        }
        pre_t = min( l[i].t , pre_t+l[i].w );
    }
    for(int i=0;i<top;i++)
        if(cmp(heap[i].red,0)==-1)
            hp+=heap[i].red*100/heap[i].w;
    printf("%.3lf\n",hp+100.0*allpow);
   
}