P1873. EKO 砍树

发表于 分类于 阅读次数： Waline： 本文字数： 266 阅读时长 ≈ 1 分钟

考点

  • 二分

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int LEN = 1e6 + 50;

int N, M, arr[LEN];

bool check(int x)
{
    ll ans = 0, diff = 0;
    for (int i = 0; i < N; ++i)
        ans += (diff = arr[i] - x) <= 0 ? 0 : diff;
    return ans >= M;
}

int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        cin >> arr[i];
    int l = 0, r = 1e9;
    while (l <= r)
    {
        int mid = l + (r - l) / 2;
        if (check(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    cout << r;
    return 0;
}

思路

当满足木材的要求时，木机锯片要尽可能地高；要么是DP或贪心，要么是二分！这里很显然没有状态转移与单调性，所以只能是二分

锯片高度从0 ~ 1e9，那么就二分锯片高度，每次判断当前高度下的木材，时间复杂度也只有\(O\left( n\log n \right)\)：

  • 如果木材多了，说明锯片高度过低了，向右边界移动
  • 如果木材恰好满足需求，也要向右边界移动（因为题目说尽可能地高）
  • 如果木材少了，说明锯片高度过高了，向左边界移动