首页 > 代码库 > 【hoj】1604 cable master

【hoj】1604 cable master

简单,二分法,但是在oj上交的时候会有精度的限制,所以只能把数扩得大一点,而且在扩的时候为防止尾数会自动生成一些非零数,所以还是自己吧扩到的位置设置为0,还有输出时因为%.2lf会自己有4设5入,所以可以自己算出小数点后两位的数值,在输出,保证要求的精度

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MAX 10010
using namespace std;

long long input[MAX];
int m,n;
bool cmp(int a,int b)
{
    return a<b;
}
bool judge(int mid)
{
    int x = 0;
    for(int i = 0;i < n;i++){
        x += input[i] / mid;
    }
    if(x >= m)
        return true;
    else
        return false;
}
int main()
{
//#ifndef ONLINE_JUDGE
  //  freopen("in.txt","r",stdin);
//#endif

    long long high,low,mid,res;
    double a;
    while(cin>>n>>m){
        high = 0;
        low = 0;
        for(int i = 0;i < n;i++){
            cin>>a;
            input[i] = (a+1e-8)*10000;
            high = high > input[i]?high : input[i];
        }
        sort(input,input+n,cmp);
        res = 0;
        low = 10000/100;
        while(low <= high){
            mid = (low+high)/2;
            if(judge(mid)){
                res = mid;
                low = mid+1;
            }
            else
                high = mid-1;
        }
        int th = res/10000;
        int hu = (res - th * 10000)/1000;
        int te = (res - th * 10000 - hu * 1000)/100;
      printf("%d.%d%d\n",th,hu,te);

    }
}