USACO2010Oct-Soda Machine

2023-06-23 08:08:53

usaco2010 Oct-Soda Machine

Time Limit: 3 Sec Memory Limit: 128 MB

Description

To meet the ever-growing demands of his N (1 <= N <= 50,000) cows,Farmer John has bought them a new soda machine. He wants to figure out the perfect place to install the machine.

The field in which the cows graze can be represented as a one-dimensional number line. Cow i grazes in the range A_i..B_i (1 <= A_i <= B_i; A_i <= B_i <= 1,000,000,000) (a range that includes its endpoints), and FJ can place the soda machine at any integer point in the range 1..1000000000. Since cows are extremely lazy and try to move as little as possible, each cow would like to have the soda machine installed within her grazing range.

Sadly, it is not always possible to satisfy every cow's desires. Thus FJ would like to know the largest number of cows that can be satisfied.

To demonstrate the issue, consider four cows with grazing ranges 3..5, 4..8, 1..2, and 5..10; below is a schematic of their grazing

ranges:

1   2   3   4   5   6   7   8   9  10  11  12  13

         |---|---|---|---|---|---|---|---|---|---|---|---|-...

                 aaaaaaaaa

                     bbbbbbbbbbbbbbbbb

         ccccc           ddddddddddddddddddddd

Sample Output

As can be seen, the first, second and fourth cows share the point 5,

but the third cow's grazing range is disjoint. Thus, a maximum of

3 cows can have the soda machine within their grazing range.

OUTPUT DETAILS:

If the soda machine is placed at location 5, cows 1, 2, and 4 can be
satisfied. It is impossible to satisfy all four cows.

Input

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: A_i

and B_i

Output

* Line 1: A single integer representing the largest number of cows

whose grazing intervals can all contain the soda machine.

Sample Input

3 5

4 8

1 2

5 10

Sample Output

題意：有N個人要去膜拜JZ，他們不知道JZ會出現在哪裡，是以每個人有一個活動範圍，隻要JZ出現在這個範圍内就能被膜拜，偉大的JZ當然希望膜拜他的人越多越好，但是JZ不能分身，是以隻能選擇一個位置出現，他最多可以被多少人膜拜呢，這個簡單的問題JZ當然交給你了。

題解：由于a，b過大，我們先将資料離散化之後，再求一遍字首和就可以了。

Code：

var
  n,i,a,b,max,cnt,dov:longint;
  f,g,x,p:array[0..100005] of longint;
procedure sort(l,r:longint);
var i,j,u,t:longint;
begin
  i:=l;j:=r;u:=f[(l+r) div 2];
  repeat
    while (f[i]<u) do inc(i);
    while (f[j]>u) do dec(j);
    if not(i>j) then
    begin
      t:=f[i];f[i]:=f[j];f[j]:=t;
      t:=x[i];x[i]:=x[j];x[j]:=t;
      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,b);
    inc(cnt);
    f[cnt]:=a;x[cnt]:=1;
    inc(cnt);
    f[cnt]:=b+1;x[cnt]:=-1;
  end;
  sort(1,cnt);
  for i:=1 to cnt do
    if f[i]<>f[i-1] then
    begin
      inc(dov);
      p[dov]:=x[i];
    end else inc(p[dov],x[i]);
  for i:=1 to dov do
  begin
    g[i]:=g[i-1]+p[i];
    if g[i]>max then max:=g[i]
  end;
  writeln(max);
end.

USACO2010Oct-Soda Machine