P2440. 木材加工

发表于 分类于 阅读次数： Waline： 本文字数： 207 阅读时长 ≈ 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
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

const int LEN = 1e5 + 10;

typedef long long ll;

int N, K, arr[LEN];

bool check(int x)
{
    ll res = 0;
    for (int i = 0; i < N; ++i)
        res += ceil(arr[i] / x);
    return res >= K;
}

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

思路

找满足条件下的最大值，基本是考察二分；二分切割长度l，范围从1到原木的最大长度

  • 如果当前长度l切割出来的数量大于需求，说明l小了，需要向右边界移动
  • 如果等于需求，也要向右边界移动（因为求最大）
  • 如果小于需求，说明l大了，向左边界移动