[TIOJ 1529] 邪惡的魔人姜姜

作法：

這題的想法類似 2014 年入營考的最後一題。首先可以把破壞的順序調成按照截止時間遞增的，因為如果有一個炸彈比另一個炸彈截止時間早，卻被比較早爆破，那麼把這兩個炸彈順序交換不會讓情況更差，還有可能更好。再來則是如果要讓整體時間減少特定一個值的話，那麼用「需要爆破時間越長」的炸彈來耗HP是最好的，因為同樣都是消耗某個比例的時間，需要時間越長那麼省下來的時間就越多。所以首先把炸彈按照截止時間排序，每次作下一個炸彈就先假設不耗HP，再看如果超出了限制時間的話要對哪顆炸彈耗HP來把時間補回來，所以我們需要一個 priority queue，裡面放的是目前為止爆破的所有炸彈的二元祖： ( 此炸彈還有幾%可以用來減少時間 , 原始需要的爆破時間 )這個東西，並且讓「 原始需要的爆破時間」越多的越早出隊，一直 pop 到滿足了新的炸彈的限制條件為止就好了。

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=500000+10 ;
const DB eps=1e-7 ;
 
struct P
{
    DB x,y ;
    bool operator < (const P &rhs) const
    {
        if(fabs(y-rhs.y)<eps) return x<rhs.x ;
        return y<rhs.y ;
    }
};
 
P a[maxn];
priority_queue<P> pq ;
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y) ;
    sort(a+1,a+n+1) ;
    DB now=0.0 , ans=0.0 ;
    for(int i=1;i<=n;i++)
    {
        now+=a[i].x ;
        pq.push((P){1.0,a[i].x}) ;
        if(now>a[i].y)
            while(fabs(now-a[i].y)>eps)
        {
            P u=pq.top() ; pq.pop() ;
            DB t=now-a[i].y ;
            if( t > u.y*u.x ) now-= u.y*u.x , ans+=100.0*u.x ;
            else now=a[i].y , pq.push((P){u.x-t/u.y,u.y}) ,
                    ans+= 100.0*(t/u.y) ;
        }
    }
    printf("%.3f\n",ans) ;
}