加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

POJ PKU 1064 二分

(2010-04-21 22:59:26)
标签:

poj

pku

1064

it

分类: 杂题

题目描述: 给你n条电缆,让你分成至少k条一样长度的电缆, 问这个最长的长度是多少。

解题报告:

二分枚举长度,然后用这个长度判断分成的条数m,如果m >= k,则这个答案符合,需要尝试更长的答案,所以左边界更新。

否则答案偏大,更新右边界。

符合答案的里面最大的就是答案。

代码如下:

#include<iostream>
using namespace std;
int n, k, x[10000];
double temp;
bool judge(int mid)
{
    if (mid == 0)
        return true;
    int sum = 0;
    for(int i = 0; i < n; i )
        sum = x[i] / mid;
    return sum >= k;
}
int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i )
        scanf("%lf", &temp), x[i] = (int)(temp * 100);
    int l = 0, r = 10000000, ans = 0;
    while(l <= r)
    {
        int mid = (l r) / 2;
        if (judge(mid))
            l = mid 1, ans = (mid > ans ? mid : ans);
        else
            r = mid - 1;
    }
    printf("%.2f\n", ans / 100.0);
}

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有