【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[1..110000]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)>>1]; mid2:=y[(l+r)>>1];
 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:=1 to up do
 begin
  x[i]:=l[i]; y[i]:=r[i];
 end;
 t:=up;
 inc(t); x[t]:=n+1; y[t]:=n+1;
 qsort(1,t);
 now:=0; ans:=0;
 for i:=1 to t do
 begin
  if x[i]>now+1 then
  begin
   if x1=0 then exit(false);
   len:=x[i]-now-2;
   tmp:=len div x1+1;
   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:=1 to m do read(l[i],r[i]);
 left:=1; right:=m; last:=m+1;
 while left<=right do
 begin
  mid:=(left+right)>>1;
  if isok(mid) then begin last:=mid; right:=mid-1; end
   else left:=mid+1;
 end;
 if last=m+1 then writeln('Poor Douer!')
  else writeln(last);
 close(input);
 close(output);
end.

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