2017.07.10【NOIP提高组】模拟赛B组 射击 题解

原题：

http://172.16.0.132/senior/#contest/show/2045/1

题目描述：

有问题，找副连，无聊的时候当然也可以找他啦。小W找到了他的叔叔——东厂厂长——宇宙超级无敌老WS yy。他们叔侄两个商量之后决定用弹弓打破社区里的一些窗户，但是弹弓每秒只能彻底打破一扇窗户。而且如果某户窗户的主人回来了的话，他们就不能进行破坏了（不然会死得很惨的）。因为有的人装的玻璃好，有的人装的玻璃差，有的人装的玻璃高，有的人装的玻璃矮，所以你不能要求他们叔侄两个打破不同的窗户获得的快乐值必须相同。现在他们想知道在能活着的情况下能够获得的最大快乐值。

输入：

第一行一个正整数n，表示共有n个窗户。
接下来n行，每行两个整数，第一个为窗子的主人回来的时刻（秒），第二个为破坏该窗户所能获得的快乐值。

输出：

最大的快乐值。

样例输入：

4
1 19
2 10
1 20
2 15

样例输出：

35

样例说明：

在第0个时刻，他们选择破坏掉3号窗户，在第1个时刻，因为1号窗户的主人已经回来了，所以不能去破坏1号窗户，只能去破坏2号窗户或4号窗户，显然选择4号窗户。总的快乐值就是20+15=35。

数据范围限制：

20%的数据，n<=100。
40%的数据，n<=50000。
100%的数据，n<=200000，快乐值的绝对值不超过32767，时刻非负且小于2^31。

分析：

我们把窗户按照时间排序，之后反过来做。
对于每一 个时间段，我们不妨假设它的长为cur。那么显然，在这个时间段后面的所有窗户都是可以打的。所以我们可以用一个堆来维护当前时间段后面的窗 户：对于每个时间段cur，我们取最大的cur个窗户来打破。

实现：

var
        ans:int64;
        i,j,t,n,m,l,r:longint;
        a:array[0..200001] of longint;
        x,y:array[0..200001] of longint;
procedure ins(x:longint);
var
        i:longint;
begin
        inc(t);
        a[t]:=x;
        i:=t;
        while (i>1) and (a[i]>a[i shr 1]) do
        begin
                a[0]:=a[i];
                a[i]:=a[i shr 1];
                a[i shr 1]:=a[0];
                i:=i shr 1;
        end;
end;
function del:longint;
var
        i,s:longint;
        f:boolean;
begin
        del:=a[1];
        a[1]:=a[t];
        dec(t);
        i:=1;
        f:=true;
        while f and (i shl 1<=t) do
        begin
                if (i shl 1+1>t) or (a[i shl 1]>a[i shl 1+1]) then s:=i shl 1
                else s:=i shl 1+1;
                if a[s]>a[i] then
                begin
                        a[0]:=a[i];
                        a[i]:=a[s];
                        a[s]:=a[0];
                        i:=s;
                end
                else f:=false;
        end;
end;
procedure qsort(l,r:longint);
var
        i,j,mid:longint;
begin
        i:=l;
        j:=r;
        mid:=x[l+random(r-l+1)];
        repeat
                while (x[i]<mid) do inc(i);
                while (x[j]>mid) do dec(j);
                if i<=j then
                begin
                        x[0]:=x[i];x[i]:=x[j];x[j]:=x[0];
                        y[0]:=y[i];y[i]:=y[j];y[j]:=y[0];
                        inc(i);dec(j);
                end;
        until i>j;
        if l<j then qsort(l,j);
        if i<r then qsort(i,r);
end;
begin
        randomize;
        readln(m);
        for i:=1 to m do
        begin
                readln(l,r);
                if r>0 then
                begin
                        n:=n+1;
                        x[n]:=l;
                        y[n]:=r;
                end;
        end;
        qsort(1,n);
        for i:=1 to n do
                if x[i]>n then x[i]:=n;
        j:=n;
        for i:=x[n] downto 1 do
        begin
                while (x[j]>=i) and (j>=1) do
                begin
                        ins(y[j]);
                        dec(j);
                end;
                if t>=1 then ans:=ans+del;
        end;
        writeln(ans);
end.