ksum

题目大意

给出一个长度为 n 的数组，现在

求前 k 大的数。

数据范围

JZOJ 4815 【NOIP2016提高A组五校联考4】ksum

题解

我们将所有的数按照其对应区间的左端点来分类，那么一共会分成n类。
维护一个大小为 n 的堆，一个位置维护一个类别。
一开始将区间[ 1 , n ]，[ 2 , n ]，[ 3 , n ]…，[ n - 1 , n ]，[ n , n ]这些区间对应的数放入堆内，每次把堆顶（即最大的数）取出，将其右边界- 1 ，再丢回堆内维护，可以证明，取出来的前 k 个数就是前 k 大的数。

Code(Pascal)

var
    d:array[0..200100,1..3] of int64;
    n,j,k,l,i,m:longint;
    o:int64;
    s:array[0..120000] of int64;
procedure up(o:longint);
var
        y:longint;
begin
while (o>1) and (d[o,1]>d[o div 2,1]) do
begin
            y:=o div 2;
            d[0]:=d[o];
            d[o]:=d[y];
            d[y]:=d[0];
            o:=y;
end;
end;
procedure down(o:longint);
var
        y:longint;
begin
while ((o*2<=n) and (d[o*2,1]>d[o,1])) or
        ((o*2+1<=n) and (d[o*2+1,1]>d[o,1])) do
begin
            y:=o*2;
if (o*2+1<=n) and (d[o*2+1,1]>d[o*2,1]) then
            inc(y);
            d[0]:=d[y];
            d[y]:=d[o];
            d[o]:=d[0];
            o:=y;
end;
end;
begin
    readln(n,k);
for i:=1 to n do
read(s[i]);
for i:=n downto 1 do
begin
        o:=o+s[i];
        inc(m);
        d[m,1]:=o;
        d[m,2]:=i;
        d[m,3]:=n;
        up(m);
end;
for i:=1 to k do
begin
write(d[1,1],' ');
        d[1,1]:=d[1,1]-s[d[1,3]];
if d[1,1]=d[1,3] then
begin
            d[1,1]:=-1;
            d[1,2]:=-1;
            d[1,3]:=-1;
end
else dec(d[1,3]);
        down(1);
end;
end.

秒客网