POJ 1064 Cable master（二分答案）

骑猪看日落 2021-10-23 17:56 217阅读 0赞

### 嗯... ###

## ##

### 题目链接：[http://poj.org/problem?id=1064][http_poj.org_problem_id_1064] ###

## 其实这是一道很好想的二分答案的一道题... ##

### 二分的区间就是1~max\_l，从1开始是因为所有小于1的都需要按0计算，没必要讨论了... ###

### 每次二分出来的答案看它能否把电缆切成大于等于k块，如果可以，我们不能保证它是最优的答案，所以要向更大的地方二分；如果现在都不可以，我们必须向更小的地方二分，才有可能可以。 ###

## ##

### 这道题注意二分一般在整数中二分，所以我们先把它们都乘100，如果要求精度更高，则乘的数更大，然后再整数二分，最后输出的时候再除回去即可...注意初始化... ###

## AC代码： ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 
     4 using namespace std;
     5 
     6 int ans, n, k, a[10004], max_l;
     7 
     8 inline void er_fen(){
     9     int l = 1, r = max_l;
    10     while(l <= r){
    11         int cnt = 0;
    12         int mid = (l + r) >> 1;
    13         for(int i = 1; i <= n; i++){
    14             cnt += a[i] / mid;
    15         }
    16         if(cnt >= k){
    17             ans = max(ans, mid);
    18             l = mid + 1;
    19         }
    20         else r = mid - 1;
    21     }
    22 }
    23 
    24 int main(){
    25     while(scanf("%d%d", &n, &k) != EOF){
    26         max_l = -1, ans = 0;
    27         for(int i = 1; i <= n; i++){
    28             double len;
    29             scanf("%lf", &len);
    30             a[i] = len * 100;
    31             max_l = max(max_l, a[i]);
    32         }
    33         er_fen();
    34         printf("%.2f\n", (double) ans / 100.0);
    35     }
    36     return 0;
    37 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11336735.html

[http_poj.org_problem_id_1064]: http://poj.org/problem?id=1064
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/260a3fb919714bd7b02cf692299eded9.png