POJ 2970 The lazy programmer 优先队列

--------------

const double EPS = 1e-7;
const int maxn=150000;

int dcmp(double a,double b){
    if (abs(a-b)<EPS) return 0;
    if (a>b) return 1;
    else return -1;
}
struct Dat{
    int a,b,d;
    double c;
    bool operator<(const Dat& rhs)const{
        return a<rhs.a;
    }
    Dat(){c=0;}
    Dat(int x,int y,int z){
        a=x;b=y;d=z;c=0;
    }
};
bool cmp(const Dat& a,const Dat& b){
    return a.d<b.d;
}
priority_queue<Dat>que;

int n;

Dat a[maxn];

int main(){
    while (~scanf("%d",&n)){
        while (!que.empty()) que.pop();
        for (int i=0;i<n;i++){
            scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].d);
            a[i].c=0;
        }
        sort(a,a+n,cmp);
        double sum=0;
        double T=0;
        for (int i=0;i<n;i++){
            que.push(a[i]);
            T+=(double)a[i].b;
            while (dcmp(T,(double)a[i].d)>0){
                Dat pr=que.top();
                que.pop();
                double x=(T-(double)a[i].d)/(double)pr.a;
                if (dcmp((double)pr.b/(double)pr.a,pr.c+x)>0){
                    pr.c+=x;
                    sum+=x;
                    T-=x*(double)pr.a;
                    que.push(pr);
                    break;
                }
                else {
                    x=(double)pr.b/(double)pr.a-pr.c;
                    pr.c+=x;
                    sum+=x;
                    T-=x*(double)pr.a;
                }
            }
        }
        printf("%0.2f
",sum);
    }
	return 0;
}

--------------