bzoj 3190 维护栈

　　我们可以将每一辆赛车看成一条直线，斜率为速度，纵截距为初始位置，那么问题就转化为求这n条直线处于最上面的直线。最上面是指在坐标系中，假设从x轴向下看，能看到的直线，只露一个点也算能看见。那么就类似水平可见直线这道题了。先按照斜率排序，然后维护直线的栈就行了。

/**************************************************************
    Problem: 3190
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:84 ms
    Memory:548 kb
****************************************************************/
 
//By BLADEVIL
var
    n                       :longint;
    a, b, num               :array[0..10010] of longint;
    quea, queb              :array[0..10010] of longint;
    tot                     :longint;
    quex                    :array[0..10010] of double;
    ans                     :array[0..10010] of longint;
    i, j                    :longint;
    flag                    :array[0..10010] of boolean;
    maxi                    :longint;
     
procedure swap(var a,b:longint);
var
    c                       :longint;
begin
    c:=a; a:=b; b:=c;
end;
     
procedure qs(low,high:longint);
var
    i, j, xx, yy            :longint;
begin
    i:=low; j:=high; xx:=a[(i+j) div 2];
    yy:=b[(i+j) div 2];
    while i<j do
    begin
        while (a[i]<xx) or (a[i]=xx) and (b[i]>yy) do inc(i);
        while (a[j]>xx) or (a[j]=xx) and (b[j]<yy) do dec(j);
        if i<=j then
        begin
            swap(a[i],a[j]);
            swap(b[i],b[j]);
            swap(num[i],num[j]);
            inc(i); dec(j);
        end;
    end;
    if i<high then qs(i,high);
    if j>low then qs(low,j);
end;
     
procedure insert(i:longint);
var
    k                       :longint;
    x                       :double;
begin
    if a[i]=quea[tot] then exit;
    if tot>1 then
    begin
        x:=(queb[tot-1]-b[i])/(a[i]-quea[tot-1]);
        while (tot>1) and (x<quex[tot]) do
        begin
            dec(tot);
            x:=(queb[tot-1]-b[i])/(a[i]-quea[tot-1]);
        end;
    end;
    inc(tot);
    quea[tot]:=a[i];
    queb[tot]:=b[i];
    quex[tot]:=(queb[tot-1]-b[i])/(a[i]-quea[tot-1]);
    ans[tot]:=num[i];
end;
     
begin
    read(n);
    for i:=1 to n do read(b[i]);
    for i:=1 to n do read(a[i]);
    maxi:=0;
    for i:=1 to n do if b[i]>b[maxi] then maxi:=i; 
    flag[maxi]:=true;
    for i:=1 to n do if b[i]=b[maxi] then flag[i]:=true;
    for i:=1 to n do num[i]:=i;
    qs(1,n);
    quea[1]:=a[1]; queb[1]:=b[1]; 
    quex[1]:=-maxlongint; ans[1]:=num[1];
    tot:=1;
    for i:=2 to n do insert(i);
    for i:=1 to tot do if quex[i]>=0 then break;
    for j:=i to tot do flag[ans[j]]:=true;
    qs(1,n);
    for i:=1 to n do
        if flag[i] then
        begin
            j:=i-1;
            while (a[j]=a[i]) and (b[j]=b[i]) do
            begin
                flag[j]:=true;
                dec(j);
            end;
            j:=i+1;
            while (a[j]=a[i]) and (b[j]=b[i]) do
            begin
                flag[j]:=true;
                inc(j);
            end;
        end;
    tot:=0;
    for i:=1 to n do if flag[i] then inc(tot);
    writeln(tot);
    for i:=1 to n do if flag[i] then break;
    write(i);
    for j:=i+1 to n do if flag[j] then write(' ',j);
    writeln;
end.

bzoj 3190 维护栈

推荐阅读