A - Cable master

题目链接:https://vjudge.net/contest/351324#problem/A

题目描述:

有N根电线,它们的长度分别为Li。如果从它们中切割出K条长度相等的电线的话,这K根电线每根最长能有多长?答案保留小数点后两位。
限制条件:
1<=N<=10000
1<=K<=10000
1<=Li<=100000
样例输入:
4 11
8.02
7.43
4.57
5.39
样例输出
2.00

解题思路:

假设每根切割的长度为x,既x=mid=(l+r)/2,按这个长度切割获得的电线的数量如果比要求的数量大,则意味着当前分割的长度不是最大值,答案在mid~r之间(l=mid),反之答案在l~mid之间(r=mid)。通过不断缩小l~r的范围获得最终答案。

代码:

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
double a[10000];
int n,k;
bool check(double x){
    int cnt;
    cnt=0;
    for(int i=0;i<n;i++){
        cnt=cnt+int(a[i]/x);
    }
    return cnt>=k;
}
int main(){
    #ifdef HH
    freopen("G:/input.txt","r",stdin);
    #endif // HH
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%lf",&a[i]);
    }
    double l,r,mid;
    l=0;
    r=100000;
    while(r-l>1e-8){
        mid=(r+l)/2;       //右移运算是向下取整的,但除法向0取整
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.2f\n",floor(r*100)/100);   //向下取整,保留小数点后两位
    return 0;
}
Last modification:January 15th, 2020 at 12:56 am
如果觉得我的文章对你有用,请随意赞赏