Codeforces Round #409 (Div. 2) C. Voltage Keepsake 二分

My Solution

题意：每个设备初始电量为bi，每秒消耗ai，然后充电器每秒可以给一个设备充电p，问所有设备同时工作的最长时长。

二分

很显然的要用二分来做，然后check函数该怎么写呢?

这里题目中说 You can switch which device is charging at any arbitrary unit of time (including real numbers) ，

这就表示可以整体处理，也就是说，首先把设备按照只用初始电量的工作时间(real number)排序，

然后对于每个mid 进行check的时候，把0~i这些工作时长不到mid的设备进行充电，可以得到总时长 sigma{(mid - val[i].dist) * val[i].a} ,然后与mid*p比较即可。

这里相当于在一个设备需要的时候给它充电eps，然后再给另一个需要的设备充电eps，如果sigma < mid*p，即可使所有设备稳定工作mid秒的时长。

此外，

1、对于p >= sigma{ai}的情况表示必定可以充足，此时时间为INF。

2、对于二分时候的EPS取1e-4即可，一般EPS取题目给出的误差精度即可，可自行计算证明。

然后这里二分的r的极限不大好计算，由于double可以保持15位有效数字以上，所以这里取EPS为1e-a时，r可以取(1e15-a)+1。//这里+1是笔者二分时习惯^_^

复杂度 O(nlogn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;
const double EPS = 1e-4;
const double INF = 1e11 + 1;

struct p{
    int a, b;
    double dist;
}val[MAXN];

inline bool cmp(const p &a, const p &b)
{
    return a.dist < b.dist;
}

int n, p;
inline bool check(const double &x)
{
    double sum = 0;
    int i;
    for(i = 0; i < n; i++){ if(val[i].dist - x > 0) break;
        sum += (x - val[i].dist) * val[i].a;
    }
    if(x * p > sum) return true;
    else return false;

}


int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int i;
    LL sum = 0;
    cin >> n >> p;
    for(i = 0; i < n; i++){ cin >> val[i].a >> val[i].b;
        val[i].dist = val[i].b * 1.0 / val[i].a;
        sum += val[i].a;
    }
    sort(val, val + n, cmp);

    if(p - sum >= 0){
        cout << -1 << endl;
    }
    else{
        double ans = 0, l = 0, r = INF, mid;
        while(l + EPS < r){
            mid = (l + r) / 2;
            if(check(mid)){
                ans = mid;
                l = mid;
            }
            else r = mid;
        }
        cout << fixed << setprecision(10) << ans << endl;
    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx