TIOJ-1529 邪惡的魔人姜姜

TIOJ-1529 邪惡的魔人姜姜

AC code:

//By SCJ  

#include<bits/stdc++.h>  

using namespace std;  

struct P{  

   double x,y;  

   bool operator < (const P &a)const{  

       return y<a.y;  

   }  

}d[500001];  

int main()  

{  

ios::sync_with_stdio(0);  

cin.tie(0);  

   int n;cin>>n;  

   for(int i=0;i<n;++i)  

       cin>>d[i].x>>d[i].y;  

   sort(d,d+n);  

   priority_queue<P> pq;  

   double T=0,ans=0;  

   for(int i=0;i<n;++i)  

   {  

       pq.push({1.0,d[i].x});  

       if(T+d[i].x<=d[i].y) T+=d[i].x;  

       else  

       {  

           double g=T+d[i].x-d[i].y;  

           while(g)  

           {  

               P tp=pq.top();pq.pop();  

               double h=g/tp.y;  

               if( h >= tp.x ) g-=tp.y*tp.x,ans+=tp.x;  

               else ans+=h,pq.push({tp.x-h,tp.y}),g=0;  

           }  

           T=d[i].y;  

       }  

   }  

   cout<<fixed<<setprecision(3)<<ans*100<<'\n';  

}