COCI_2007_排队 一题总结

COCI_2007_排队_题目大意：

在一个队伍里有n个人，当且仅当两人之间没有人身高比这两人身高高时，他们可互相看见，需统计出有多少对人可以互相看见。

Way one：

比较容易想到的方法之一.

维护一个栈，使得栈从大到小。因为题目的描述限制，这个栈有可能是有相等的元素并排在一起.

对于当前第x个人，设第x个人的身高为w[x].

维护方法：判断w[x]的值是否大于栈顶，如果大于栈顶则抽出，以此类推，直到栈顶大于w[x]或栈里没有元素为止.

记录答案：判断w[x]的值大于等于栈顶，如果大于栈顶则记录并抽出（不用真的抽出），以此类推，直到不能记录.

易证次方法可以得到正确的答案.

此方法期望复杂度也非常低，应为O(n)级别的效率，但是，由于维护和记录所对应的条件不一，可能导致如下情况：

对于当前的第x个人，有可能其身高与栈里的所有元素都相等，但是记录答案的时候并不会抽出，对于这种极端的数据，效率从O(n)变成O(n²)，大大降低.

如何解决这种情况，使得对于这种极端数据，也不会有影响呢？————看Way two.

代码：

var
        a,b:array[0..500000] of longint;
        n,i,j,x,ans:longint;
begin
        readln(n);
        read(x);
        a[0]:=1;
        a[1]:=x;
        b[0]:=1;
        b[1]:=1;
        for i:=2 to n do
        begin
                read(x);
                inc(ans);
                for j:=a[0] downto 1 do
                        if (x>=a[j]) then
                        begin
                                if b[j]<>i-1 then inc(ans);
                        end
                        else
                        begin
                                if b[j]<>i-1 then inc(ans);
                                break;
                        end;
                while (x>a[a[0]]) and (a[0]>0) do
                begin
                        dec(a[0]);
                        dec(b[0]);
                end;
                inc(a[0]);
                a[a[0]]:=x;
                inc(b[0]);
                b[b[0]]:=i;
        end;
 
        writeln(ans);
end.

Way two：

对于Way one的一种改良.

究其第一种方法的根本，问题出在身高相等这一条件上，解决了这一条件所带来的问题，则此题就可完美解决.

为了解决这一问题，我们可以多设置一个tot数组，用来记录当前栈里的每个元素所对应的个数.

也可以理解为把一段相等身高的人的个数用tot数组储存起来.

于是，在“记录答案”这一步的时候，不是把答案+1，而是加上tot[栈顶].

除了“记录答案”一步骤的改变，在维护方面，也有如下改动：

可以想象，对于第x个人的身高——w[x]，我们如果一贯按照之前的维护方法，则对于tot数组，对答案的贡献就不准确了。所以，我们在对于第x个人身高时有两种情况——“维护方法”、w[x]=栈顶.

第一种情况，则直接用之前的方法即可，只是多加一步把tot[栈顶]赋值为1罢了。

第二种情况则需细致讨论一下：

当当前第x个人的身高与栈顶相同时，则我们只需把tot[栈顶]加1，但是，仅仅这样就够了吗？

看如下数据：

7

2 4 1 2 2 5 1

如果只是按照上述步骤做，最终的答案模拟为9，但实际上答案为10.

原因就在于我们在对第4个人与第5个人的身高记录时，忽略了2与2其实也可以互相看到.

在看一个例子：

5

5 5 5 5 5

明显，答案是4+3+2+1，由此可以看出：在第二种情况上，每次要把ans再记录一下——加上tot[栈顶]才可，如果还不明白的话，可以在草稿纸上多列几个数据，仔细探究探究就明白了。

最后，如果栈里的个数大于1，则还需把答案+1，至于为什么，请自己探索。

代码：

var
        a,tot:array[0..500000] of longint;
        i,n,p,x:longint;
        ans:int64;
begin
        readln(n);
        readln(a[1]);
        tot[1]:=1;
        p:=1;
        for i:=2 to n do
        begin
                readln(x);
                while (p>0) and (a[p]<x) do
                begin
                        inc(ans,tot[p]);
                        tot[p]:=0;
                        a[p]:=0;
                        dec(p);
                end;

                if a[p]<>x then
                begin
                        inc(p);
                        a[p]:=x;
                        tot[p]:=1;
                end
                else
                begin
                        inc(ans,tot[p]);
                        inc(tot[p]);
                end;

                if p>1 then inc(ans);
        end;
        writeln(ans);
end.

当然，在此方法上还可以做一个优化——在输入的时候就把并列的数的答案先保存好，然后每个并列的数只保留一个数在一个新的数组里，然后再在这个新的数组里进行Way two的步骤，则又可以优化一些时间。

Way three：

根据Way two所运用栈的思想且这个栈是从大到小，是有序的.

所以，我们可以想到二分.

很明显，我们只需对栈进行二分，找到小于等于x的最高位（这个最高位很明显是r）然后记录答案（这里记录答案直接循环求就可以了）记录完之后并根据Way two的两种更新方法更新栈和tot的值就可以了。

代码：

var
        a,tot:array[0..500000] of longint;
        i,k,n,p,t,x,l,r,mid:longint;
        ans:int64;
begin
        readln(n);
        readln(a[1]);
        tot[1]:=1;
        p:=1;
        for i:=2 to n do
        begin
                readln(x);
                t:=p;
                l:=1;
                r:=p;
                while l<=r do
                begin
                        mid:=(l+r) >> 1;
                        if a[mid]<x then r:=mid-1 else l:=mid+1;
                end;

                p:=r;
                for k:=p+1 to t do
                        inc(ans,tot[k]);
                if a[p]<>x then
                begin
                        inc(p);
                        a[p]:=x;
                        tot[p]:=1;
                end
                else
                begin
                        inc(ans,tot[p]);
                        inc(tot[p]);
                end;

                if p<>1 then inc(ans);
        end;
        writeln(ans);
end.

Way four：

对于Way three的改良.

很明显，way two运用了二分的思想，但是我们还是可以在求解答案的时候做一个优化.

我们可以想到前缀和.

把tot数组用前缀和的方式储存，然后求答案的时候只需注意一下就好了，具体看实现代码：

var
        a,tot:array[0..500000] of longint;
        i,k,n,p,t,x,l,r,mid:longint;
        ans:int64;
begin
        readln(n);
        readln(a[1]);
        tot[1]:=1;
        p:=1;
        for i:=1 to n-1 do
        begin
                readln(x);
                t:=p;
                l:=1;
                r:=p;
                while l<=r do
                begin
                        mid:=(l+r) >> 1;
                        if a[mid]<x then r:=mid-1 else l:=mid+1;
                end;

                p:=r;
                if p<t then inc(ans,tot[t]-tot[p]);
                if a[p]<>x then
                begin
                        inc(p);
                        a[p]:=x;
                        tot[p]:=tot[p-1]+1;
                end
                else
                begin
                        inc(ans,tot[p]-tot[p-1]);
                        inc(tot[p]);
                end;

                if p<>1 then inc(ans);
        end;
        writeln(ans);
end.