首页 > 代码库 > Cable master (POJ No.1064)
Cable master (POJ No.1064)
二分搜索思想:bool C(double x)可以得到长度为x的绳子
//#define LOCAL #include<stdio.h> #include<math.h> int const MAX_N=10005; int const MAX_M=100; double const INF=100000000; int N,K; double d[MAX_N],lb,ub; //判断是否满足条件 bool C(double x)//假设截得的每段长度为x,则所有绳子中能不能截成K段 { int sum=0; for(int i=0;i<N;i++) { sum=sum+(int)(d[i]/x); } return sum>=K; } void solve() { for(int i=0;i<N;i++) { scanf("%lf",&d[i]); } lb=0.0,ub=INF; for(int i=0;i<MAX_M;i++) { double mid=(lb+ub)/2; if(C(mid))//如果能截,往上搜让mid变大一些,看行不行 lb=mid; else ub=mid;//如果不能截往下搜(找最近能截的点) } printf("%.2f\n",floor(ub*100)/100); } int main() { #ifdef LOCAL freopen("Cable master.in","r",stdin); freopen("Cable master.out","w",stdout); #endif while(~scanf("%d%d",&N,&K)) { solve(); } return 0; }
==>此处注意,如果把i设置成全局变量,注意每个函数对i的操作都会更改i的值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。