【NOIP2017练习】怎样更有力气（二分答案，线性扫描）

题意：OI大师抖儿在夺得银牌之后，顺利保送pku。这一天，抖儿问长者：“我虽然已经保送了，但我的志向是为国家健康工作五十年。请问我应该怎样变得更有力气？”

长者回答：“你啊，Too Young Too Simple,Sometimes Naive!如果你想要我教你，你要先进行艰苦的修行。”

长者的住宅中有一堵长度为n的墙。每天抖儿起床修行，会选择一段长度为x的区间染成白色。长者的住宅附近有一群香港记者，为了借助抖儿拜访长者，第i天香港记者会将区间[li,ri]染成白色来讨好抖儿（也就是说，每天墙会被抖儿和香港记者各染一次）。现在抖儿已经预先知道了香港记者的动向，他想知道他最少几天就能把墙全部染白，完成修行。

一行一个整数，表示抖儿最少几天能把墙全部染白。

如果m天之后依然无法染白，则输出“Poor Douer!”

对于所有的数据，保证n≤10^18，m≤100000，0<=x≤n且数据随机

思路：lyy出题人系列

 var x,y,l,r:array[..]of int64;

     m,left,right,last,mid,i:longint;

     n,x1:int64;

 procedure swap(var x,y:int64);

 var t:int64;

 begin

  t:=x; x:=y; y:=t;

 end;

 procedure qsort(l,r:longint);

 var i,j:longint;

     mid1,mid2:int64;

 begin

  i:=l; j:=r; mid1:=x[(l+r)>>]; mid2:=y[(l+r)>>];

  repeat

   while (mid1>x[i])or((mid1=x[i])and(mid2>y[i])) do inc(i);

   while (mid1<x[j])or((mid1=x[j])and(mid2<y[j])) do dec(j);

   if i<=j then

   begin

    swap(x[i],x[j]);

    swap(y[i],y[j]);

    inc(i); dec(j);

   end;

  until i>j;

  if l<j then qsort(l,j);

  if i<r then qsort(i,r);

 end;

 function max(x,y:int64):int64;

 begin

  if x>y then exit(x);

  exit(y);

 end;

 function isok(up:longint):boolean;

 var t,i:longint;

     now,len,tmp,ans:int64;

 begin

  for i:= to up do

  begin

   x[i]:=l[i]; y[i]:=r[i];

  end;

  t:=up;

  inc(t); x[t]:=n+; y[t]:=n+;

  qsort(,t);

  now:=; ans:=;

  for i:= to t do

  begin

   if x[i]>now+ then

   begin

    if x1= then exit(false);

    len:=x[i]-now-;

    tmp:=len div x1+;

    if now+tmp*x1>y[i] then now:=now+tmp*x1;

    ans:=ans+tmp;

    if ans>up then exit(false);

   end;

   now:=max(now,y[i]);

  end;

  exit(true);

 end;

 begin

  assign(input,'liqi.in'); reset(input);

  assign(output,'liqi.out'); rewrite(output);

  readln(n,m,x1);

  for i:= to m do read(l[i],r[i]);

  left:=; right:=m; last:=m+;

  while left<=right do

  begin

   mid:=(left+right)>>;

   if isok(mid) then begin last:=mid; right:=mid-; end

    else left:=mid+;

  end;

  if last=m+ then writeln('Poor Douer!')

   else writeln(last);

  close(input);

  close(output);

 end.

【后记】
在你的帮助下，抖儿完成修行的时间是原来的0.01倍。
抖儿对长者说：“我明白了！只有每天坚持锻炼，才能获得力量。”
长者嘿嘿一笑：“你想多了。我只是想让你刷墙而已。”
说完，长者一溜烟地跑了，速度比香港记者还要快好几倍。

巴特西

【NOIP2017练习】怎样更有力气（二分答案，线性扫描）

最新文章

热门文章