题解 P1577 【切绳子】

LMB_001 · 2017-08-03 13:03:08 · 题解

看到到现在没有P党，就来一发吧，其实这道题只要先把读入的*100，再trunc一下，最后输出时候再除回来，和普通二分就没有区别了

var
 n,k,i,l,r,x:longint;t:extended;
 a:array[1..10000]of longint;
function count(x:longint):longint;//这个函数是说如果每段长度是x，最多可以切多少段
begin
 if x=0 then exit(maxlongint);//如果每段长度是0，就弹了
 count:=0;
 for i:=1 to n do count:=count+a[i] div x;
end;
begin
 readln(n,k);
 for i:=1 to n do begin 
  readln(t);
  a[i]:=trunc(t*100);//如题，读入时把实数*100再取整
 end;
 l:=0;
 r:=maxlongint;//因为二分很快，开到maxlongint没问题
 repeat
  x:=(l+r) div 2;//取中间点
  if count(x)>=k then l:=x+1//如果每段长度大于或等于k，就改变l的位置
   else r:=x-1;//否则做相反处理
 until l>r;
 writeln(r/100:0:2);//最后输出r，记得要除回来
end.