ACM - 晾衣服 - 二分

题目链接

题意：中文题自己看
思考：
二分标准框架：给定一个答案，用O（n）的时间遍历一遍，判断可行性

边界条件：
题中限制了，bcde相互的大小关系，意味着，横着晒更占杆子长度，但是更快
所以，对于每一件衣服单独考虑就好。
在给定的时间内，如果能竖着晒，就竖着，因为更省杆子长度。如果不行，就横着。最后累加起来看，杆子放不放得下。

小技巧：
预处理横着晒和竖着晒的时间。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 2e5 + 20;
ll a[maxn];
ll b[maxn];
ll c[maxn];
ll d[maxn];
ll e[maxn];
ll t1[maxn];//heng
ll t2[maxn];//shu
int n;
ll L, sumL = 0;

int ok(int x){
    ll cnt = 0;
    for(int i = 1; i <= n; i++){
        if (t1[i] > x) return 0;
        if (t2[i] <= x) cnt += d[i];
        else cnt += b[i];
    }
    return cnt <= L;
}

int main(){
    scanf("%d%lld", &n, &L);
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    memset(d, 0, sizeof(d));
    memset(e, 0, sizeof(e));
    memset(t1, 0, sizeof(t1));
    memset(t2, 0, sizeof(t2));
    for(int i = 1; i <= n; i++){
        scanf("%lld%lld%lld%lld%lld", &a[i], &b[i], &c[i], &d[i], &e[i]);
        t1[i] = (a[i] + c[i] - 1) / c[i];
        t2[i] = (a[i] + e[i] - 1) / e[i];
        sumL += d[i];
    }
    if (sumL > L) puts("-1");
    else{
        int l = 0, r = 1e9, mid, ans;
        while(l <= r){
            mid = (l + r) >> 1;
            if (ok(mid)){
                ans = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}