P1873 倍增答案题解

· · 题解

P1873 [COCI 2011/2012 #5] EKO / 砍树（倍增答案）

题意分析

有 N 棵树，高度为 a_{i}，所有树比 H 高的部分均会被砍下，让你求最大 H 使得至少砍下 M 米长的木材（如果再升高 1 米，得不到 M 米木材）。

思路分析

如果已知 H，只需扫一遍 a_{i}，就可以计算出能砍下多少树木，复杂度 O(N)。而如果 H 偏大，得到木头一定小于 M, 偏小则大于 M, 我们可以用二分或倍增“猜”答案。复杂度 O(N\log(N))。本题解主要讨论倍增答案。

倍增答案

核心代码

long long mid=0;//答案指针
    for(long long i=20; i>=0; i--) { //由大到小保证凑出答案（答案范围设为2^20 ~ 0）
        mid+=1<<i;//2^i
        if(check(mid))mid-=1<<i;//发现木头不足要退回
    }

我们知道，任意一个正整数均可拆分为多个 2^{n} 之和（每个只用一次，想当于二进制转换），我们现在尝试对答案进行拆分，如果当前 H=mid+2^{i} 切出的木头长度小于 M，就表明答案可以拆，反之则不能。

ACcode

#include<bits/stdc++.h>
using namespace std;
long long a[1000006];
long long n, m;
bool check(int mid) {
    long long ans = 0;
    ans = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > mid) ans += (a[i] - mid);//常规判断，注意树一定先要高于mid
    }
    return ans<m;//不能取等，因为等于也满足条件，不用退回
}
int main() {
    cin >> n >> m;
    for (long long i = 0; i < n; i++) {
        cin >> a[i];
    }
    long long mid=0;//答案指针
    for(long long i=20; i>=0; i--) { //由大到小保证凑出答案（答案范围设为2^20 ~ 0）
        mid+=1<<i;//2^i
        if(check(mid))mid-=1<<i;//发现木头不足要退回
    }
    cout << mid << endl;
    return 0;
}