题解 P1577 【切绳子】

Is_TuTouYa · 2021-02-25 19:18:08 · 个人记录

首先这肯定是一道二分题了 看各位大佬都是先乘后除的思想qwq

我这个蒟蒻就完全想不到啊qwq

在此奉上浮点数二分的做法

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

using namespace std;
const int N = 1e5+10;
int n,k; double a[N];

bool check(double mid){
    int sum = 0;      //用来判定已经分分割的数量
    for(int i = 0;i < n;i++){
        sum += a[i]/mid;   //sum被定义成int类型
    }
    return sum < k;       //如果sum < k说明mid属于一个不可行的解，返回true,反之返回false。
}

int main(){
    cin >> n >> k;
    for(int i = 0;i < n;i++) cin >> a[i];
    double l = 0,r = 100000;
    while(r-l > 1e-3){
        double mid = (l+r)/2;
        if(check(mid)) r = mid;  //返回出代表mid不可行，右边界赋值为mid
        else l = mid;
    }
    printf("%.2f\n",l-0.004);    //既然题目中将小数点后2位的舍去但我们计算完是四舍五入的数，由浮点数化整形的+0.5的思想逆推将计算玩的数-0.004再让程序四舍五入就得到了舍去两位后的数
    return 0;
}