P1873 砍树

P1873 砍树

 

设置 一个判断条件的函数C(x),返回在砍树高度为x时能否得到足够木材.这是很简单的.

bool C(long long x){
    long long sum = 0;
    for(int i = 0; i < n; i++)
        if(s[i] > x) sum += s[i] - x;
    return sum >= m;
}
// 可见x越大越可能返回false
// 题目保证有解,则存在x0,使得在[0,x0]上C(x)返回真,此外返回假

接下来要在数据范围内寻找x₀即可.

很容易看出来,n和m的取值很容易使得调用一次C(x)消耗大量时间,所以不可能枚举0~x₀.

所以是二分答案.

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

long long n, m, s[1000010], ans;

bool C(long long x){
    long long sum = 0;
    for(int i = 0; i < n; i++)
        if(s[i] > x) sum += s[i] - x;
    return sum >= m;
}

int main(){
 //   freopen("in.txt", "r", stdin);
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> s[i];

    int lb = 0, ub = 2000000000;　　　　// ub大一点影响不大
    while(ub >= lb){
        int mid = lb + ub >> 1;　　　　 // >> 1 即除以2,这个运算符的优先级很低
        if(C(mid)) lb = mid + 1;
        else ub = mid - 1;
    }

    cout << ub << endl;

    return 0;
}