首页 > 代码库 > poj1064 cable master（最大值问题：二分+贪心）

poj1064 cable master（最大值问题：二分+贪心）

2024-07-08 12:33:29   219人阅读

题意：

有n条电缆，他们的长度分别为l[i]。如果从n条电缆中切割出K条长度相同的电缆的话，这k条电缆每条最长能多长？答案小数点后保留两位有效数字。

输入：

n， k

n行：l[i]

Sample Input

4 11

8.02

7.43

4.57

5.39

Sample Output

2.00

数据范围：

1<=N<=10000;

1<=k<=10000;

1<=l[i]<=100000。

分析：

设命题：can(x)=能切割出k条长度为x的电缆。
问题转化:求can(x)成立的最大的x。
提示：为了避免实数运算误差，把电缆长度放大100倍，化为整数，最后不要忘了把结果再除以100即可。
 1 const 2   maxn=10000; 3 var 4   a:array[1..maxn] of longint; 5   n,k:longint; 6   procedure init; 7     var i:longint; x:real; 8     begin 9       assign(input,‘poj1064.in‘); reset(input);10       readln(n,k);11       for i:=1 to n do12         begin13           readln(x);14           a[i]:=trunc(x*100);15         end;16       close(input);17     end;18   function can(x:longint):boolean;19     var s,i:longint;20     begin21       s:=0;22       for i:=1 to n do23         s:=s+a[i] div x;24       exit(s>=k);25     end;26   function find:longint;27     var l,r,mid:longint;28     begin29       l:=0; r:=10000000;30       while l<r do31         begin32           mid:=(l+r+1) div 2;33           if can(mid) then l:=mid   //还可能再加长34           else r:=mid-1; // 过长无法切割k份，需缩短35         end;36       exit(l);37     end;38 begin39   init;40   writeln(find/100.0:0:2);41 end.
View Code

 


联系
我们