bzoj2298

不难发现必然是两个人之间话产生矛盾或自身话有问题
很显然，当ai>aj时，若ai<n-bj时i,j两人话矛盾
ai<ai<n-bj，这东西有没有数轴上的线段的既视感？
我们只要求出做多不相交的线段就可得到最少谎话数

var a,b,f:array[0..100010] of longint;
    i,j,k,n:longint;

function min(a,b:longint):longint;
  begin
    if a>b then exit(b) else exit(a);
  end;

function max(a,b:longint):longint;
  begin
    if a>b then exit(a) else exit(b);
  end;

procedure swap(var a,b:longint);
  var c:longint;
  begin
    c:=a;
    a:=b;
    b:=c;
  end;

procedure sort(l,r:longint);
  var i,j,x,y:longint;
  begin
    i:=l;
    j:=r;
    x:=b[(l+r) shr 1];
    y:=a[(l+r) shr 1];
    repeat
      while (b[i]<x) or (b[i]=x) and (a[i]<y) do inc(i);
      while (x<b[j]) or (b[j]=x) and (y<a[j]) do dec(j);
      if not(i>j) then
      begin
        swap(a[i],a[j]);
        swap(b[i],b[j]);
        inc(i);
        dec(j);
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

begin
  readln(n);
  for i:=1 to n do
  begin
    readln(a[i],b[i]);
    b[i]:=n-b[i];
  end;
  sort(1,n);
  j:=1;
  for i:=1 to n do
  begin
    f[i]:=f[i-1];
    while b[j]=i do
    begin
      k:=j+1;
      while (a[k]=a[j]) and (b[k]=b[j]) do inc(k);
      f[i]:=max(f[i],f[a[j]]+min(k-j,b[j]-a[j]));  //注意这个地方相同分数的数目
      j:=k;
    end;
  end;
  writeln(n-f[n]);
end.