洛谷P1577《切绳子》

十月 31, 2018 1640

突然想起《割绳子》

题面🔗

题面描述

有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？答案保留到小数点后2位。

Input / Output 格式 & 样例

输入格式

第一行两个整数N和K，接下来N行，描述了每条绳子的长度Li。

输出格式

切割后每条绳子的最大长度。

输入样例

1
2
3
4
5
4 11
8.02
7.43
4.57
5.39

输出样例

1
2.00

解题思路

首先这题涉及到了int和double之间的精度转换

所以我们可以把输入的double都乘100转为int（题目要求保留两位小数）

不难看出来这题可以枚举答案 但是显然会炸

于是我们要想点优化——二分答案！

我们选择二分绳子的最大长度

这题的单调性是显然的，我就不证了（

Check(int mid)怎么写？

我们扫一遍绳子长度L[]，令 ans=\sum_{i=1}^{n}\lfloor\frac{L[i]}{mid}\rfloor

即最终绳子被分成的段数

如果 ans \geq k （题目中的 \text{k} ）则把左边界赋值为mid + 1，否则把右边界赋值为mid - 1

这里要注意的是如果mid == 0就直接退出循环

最后cout << fixed << setprecision(2) << (double) r / 100.0 << endl;

代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <iomanip>
using namespace std;

const int MAXN = 10000 + 10;
const double MAXL = 100000.00;

int n, k;
int L[MAXN];

bool Check(int x) {
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += L[i] / x;
    return ans >= k;
}

int main(int argc, char *const argv[]) {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        double P;
        cin >> P;
        L[i] = (int) (P * 100.0);
    }
    int l = 0, r = 19260817 + 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (mid == 0) break;
        if (Check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    cout << fixed << setprecision(2) << (double) r / 100.0 << endl;
    return 0;
}