洛谷 P1873 【砍树】

P1873

传送门

题外话

话说我们也要当一当光头强？？

大体题意

就是让你砍树，统一的高度，然后让你砍树，看看订什么高度合适.

思路：

二分答案，对高度二分，如果砍得树长度不够，那就说明高度高了.

如果过长，那就说明高度设矮了（OK，开始看code）

二分板子：

while(l <= r) {
    ll mid = (l + r) >> 1;
    if(check(mid)) l=mid+1;//check是关键所在，这四行只是板子.
    else r=mid-1;
}

code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n, m, a[1000001];
inline ll read() {
    long long s = 0,f = 0;
    char ch = getchar();
    while(!isdigit(ch)) f |= (ch == '-'),ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    return f?-s:s;
}
inline bool check(ll s) {
    long long tot=0;
    for(int i = 1; i <= n; i++)
        if(a[i] <= s) continue;//如果比那个砍树的机器的长度还要小，那么说明不用砍这个树.
        else tot += a[i] - s;//如果能砍到，那么把树的长度记录下来
    return tot >= m;//如果砍树的长度比要求的长，那么返回1.反之则返回0.
}
signed int main() {
    ll r = -1, l = 0;
    n = read();
    m = read();
    for(int i = 1; i <= n; i++)
        a[i] = read(),r = max(r,a[i]);
    while(l <= r) {
        ll mid = (l + r) >> 1;
        if(check(mid))
            l=mid+1;
        else
            r=mid-1;
    }
    cout<<r;
}