poj--1064

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

思路：这些最大最小化问题大多数可以用二分查找的方法来解题

　　　用 d 表示绳子最长可以为d，然后循环利用二分搜索使得中间值不断地缩小直到到达想要的精度

　　　就是

void solve()

{

    int low=;

    int high=INF;

    for(int i=;i<;i++){

        int mid=(low+high)/;

        if (is_ok(mid))    low=mid;

        else     high=mid;

    }

    printf("%.2f\n",floor(high*)/);

}

下面是完整的代码

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int K,N;

const int INF=;

double line[];

bool is_ok(double x)//用来判断这个值是否能使条件成立

{

    int num=;

    for(int i=;i<N;i++)

    {

        num+=(int)(line[i]/x);

    }

    return num>=K;

}

void solve()

{

    double low=;

    double high=INF;

    for(int i=;i<;i++)

    {

        /*

            这个思想是二分查找，

            这是利用二分查找不断地是条件精确到需要的地步

            就像用100次的循环就是使mid的值不断地缩小

            从而找出相对精确的中间值很巧妙

        */

        double mid=(low+high)/;

        if(is_ok(mid))    low=mid;

        else high=mid;

    }

    printf("%.2f\n",floor(high*)/);

}

int main()

{

    while(cin>>N>>K)

    {

        for(int i=;i<N;i++)

            cin>>line[i];

        solve();

    }

    return ;

}

巴特西

poj--1064

最新文章

热门文章