首页 > 代码库 > 【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); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。