不是VIP会员,不能显示答案

题目解答

题目:
某地共派出M名选手参加宁波市程序设计竞赛,现在他们正赶往火车站参加比赛。火车站共有N(1<=N<=100000)个检票口。由于检票员的操作速度不同,每个检票口的通行速度也就不同,平均测量,第k个检票口的速度为每人Tk秒(范围1~10^9)。
在候车时,精于计算的选手们就开始思考,假设一开始所有检票口都处于准备状态,每个检票口一次只能通过一人。那么M (2 <= M <= 10^9)名选手至少需要多少时间全部通过检。输入N,M,以及N个检票口的检票时间。求最少全部通过时间。
输入:
7 10
3
8
3
6
9
2
4

输出:
8
var
  a:array[1..100000]of longint;
  i,n,m:longint;
  left,right,mid: int64;  
function check(midTime:int64):boolean;
var 
  sum:int64;
  i:longint;
begin
  sum:=0;
  for i:=1 to n do
    begin
      sum:= sum+midTime div a[i]   ;
      if sum>=m  then  exit(true)  ;
    end;
  exit(false);
end;

begin
  readln(n,m);
  for i:=1 to n do readln(a[i]);
  left:=0;
  right:=a[1];
  right:=right*m;
  while left<right do
    begin
      mid:=(left+right) div 2;
      if  check(mid)   then right:=mid;
      else  left:=mid+1     ;
    end;
   writeln(left)   ;   
end.
考点:
分析:
解答:
评论:
老师: