[UVa 12584]Laptop Chargers

Minimum how many chargers does he need to run all the laptops forever:
We can just sum up each discharge rate of the laptops, and then calculate how many chargers do we need to prevent total charge rate from being lower than the total discharge rate.
Explanation:
If total charge rate $<$ total discharge rate, you'll be sure to run out all your batteries someday.
Otherwise, with very fast charger switching, you can try to keep all your batteries from being lower than original conditions, and even better if possible.
For simplicity, we call the answer $\min M$

Maximum how long will he be able to run all his laptops using $M (M < N)$ chargers?
If $M\geq \min M$, the answer is, of course, $-1.000$.
Otherwise, we can come up with a simple method to get an "answer" first. That is, get total charge remaining in the laptop batteries(We call it $TR$ later), total discharge rate of laptops(We call it $TD$ later), and total charge rate of chargers(We call it $TC$ later)
Then we can get $\frac{TR}{TD-TC}$.
What's the problem if we treat it as the answer?
There exists some cases, such that one of the laptop battery is able to sustain for a very long time, even all other laptops have run out of battery with all chargers working.

So the problem is, which laptops don't need to be charged?
We can sort the laptops by the time they run out of battery without charger. For some $m$ ($m\geq M$), we can try use all chargers to make the first $m$ laptops run as long as possible, and see whether the $(m+1)$-th laptop can sustain until the first $m$ laptops are all run out of battery with all $M$ chargers working.

Find the first $m$ that the $(m+1)$-th laptop can sustain to the last. Then the answer is the time when the first $m$ are out of battery.
Otherwise, if we can't find such $m$, the "fake answer", $\frac{TR}{TD-TC}$, mentioned at first is printed.
Notice that if $TC\geq TD$ or $\frac{TR}{TD-TC}>100000$, you should always print "$-1.000$".

Time complexity: $O(N\log N+QN)$

Random inputs had been added to uDebug. :)

code:

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const double EPS=1e-9;
struct Laptop
{
    double c,t,r;
    Laptop(){}
    Laptop(const double &_c,const double &_t,const double &_r):c(_c),t(_t),r(_r){}
    bool operator<(const Laptop &l)const{return r/(c/t)<l.r/(l.c/l.t);}
};
int N;
double C;
vector<Laptop>L;
double Solve(const int m)
{
    if(m==0)return L[0].r/(L[0].c/L[0].t);
    double remain=0.0,d_rate=0.0;
    for(int i=0;i<m;i++)remain+=L[i].r,d_rate+=L[i].c/L[i].t;
    for(int i=m;i<N;i++)
    {
        const Laptop &lap=L[i];
        if(d_rate>C*m+EPS&&remain/(d_rate-C*m)<lap.r/(lap.c/lap.t))return remain/(d_rate-C*m);
        remain+=lap.r,d_rate+=lap.c/lap.t;
    }
    return remain/(d_rate-C*m);
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int querycount;
    while(scanf("%d%d",&N,&querycount)==2)
    {
        if(N==0&&querycount==0)break;
        scanf("%lf",&C);
        L.clear();
        double discharge_rate=0.0;
        for(int i=0;i<N;i++)
        {
            static Laptop l;
            scanf("%lf%lf%lf",&l.c,&l.t,&l.r);
            L.push_back(l);
            discharge_rate+=l.c/l.t;
        }
        static int kase=1;
        printf("Case %d:\n",kase++);
        if(true)
        {
            const double ans=discharge_rate/C;
            printf("%d\n",fabs(ans-round(ans))<EPS?(int)(ans+0.5):(int)ans+1);
        }
        sort(L.begin(),L.end());
        for(int m;querycount--;)
        {
            scanf("%d",&m);
            if(discharge_rate<=m*C+EPS)puts("-1.000");
            else
            {
                const double ans=Solve(m);
                if(ans>100000.0)puts("-1.000");
                else printf("%.3f\n",ans);
            }
        }
    }
    return 0;
}