「ACM 算法实践」[解题报告]时间管理大师-526互联

分析

一开始想着应该要分情况讨论，如果每台电脑的耗电量都小于 \(e\) ，那么可以知道小 Q 是可以一直学习下去的，如果存在电脑的耗电量大于等于 \(e\) ，贪心的想法是将每台电脑能用的时间从小到大排序，然后丢进优先队列里，再考虑给谁充电，这样一来情况就非常复杂了。

正确的做法是二分答案 \(t\) ，计算每台电脑运行到 \(t\) 时间需要的电量，再计算出充电需要的总时间与 \(t\) 进行比较。

之后做题的时候也应该看看答案是否单调，然后考虑能不能用二分做，而不是看到明显的二分答案的问题才考虑（这种问题很多情况下也不是用的二分）。要知道，二分的一个最大的优势就是可以在已知的「答案」下按照这个答案模拟，看能否符合条件即可，不太需要考虑各种各样的策略，从而也就简化了复杂的条件。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef double db;
typedef long long ll;

int gi() {
    char c = getchar(); int x = 0, f = 1;
    for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return x * f;
}

const int N = 1e5 + 5;
const double eps = 1e-8;

int n, e;
int a[N], b[N];

bool check(db t) {
    db need = 0;
    for (int i = 1; i <= n; ++i) {
        db tmp = (db)a[i] * t;
        if (tmp > (db)b[i]) need += (tmp - (db)b[i]) / (db)e;
    }
    return need <= t;
}

int main() {
    ll s = 0;
    bool flg = 0;
    n = gi(), e = gi();
    for (int i = 1; i <= n; ++i) {
        a[i] = gi(), b[i] = gi();
        s += a[i];
    }
    db l = 0, r = 1e10;
    if (s <= e) { puts("-1"); return 0; }
    while (r - l > eps) {
        db mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%.10lf\n", l);
    return 0;
}