9度OJ 1422 Closest Number

タイトルリンク:http://ac.jobdu.com/problem.php?pid=1422
各要素a[i]に対してa[i]に最も近いa[i]より小さい数をそれぞれ探し、左右の距離が同じであれば左側の数をとる配列を与える.
例えば2,3,1は1,2,0を出力.
構想:テーマデータは10^6であり、暴力O(n^2)が肯定的にタイムアウトした場合、我々は暴力計算の過程で大量の繰り返し計算が存在することを発見した.例えばa[]={1,4,3,2}は、a[3]の解を探す際に左に遍歴し、a[2]>a[3]は左に進み、a[1]>a[3]は実際にa[1]と比較され、a[1]がa[2]よりも大きいことが発見された場合には直接省略することができる.この問題の解は二つの部分に分けることができる.すなわち、現在の要素の左側に最も近い要素と、右側に最も近い要素と、それより小さい要素とに分けられる.この場合、左側ithの数が現在の値より大きい場合、問題はithの解を利用して、下付きkをithの解の下付き文字に直接位置決めすることができ、a[k]が現在の要素より小さくなければ左に遍歴し続ける性質を発見することができる.解を見つけたり境界を越えたりするまで順番にジャンプします.L[]とR[]配列で、左側と右側が最も近く、値がa[i]未満の下付き文字をそれぞれ格納します.これは動的計画の思想だろう.コードは次のとおりです.

#include 
#include 
 
#define M 1000010
#define INF 9999999
 
int a[M],l[M],r[M];
 
int Min(int a,int b)
{
    return (a<=b)?-1:1;
}
int main()
{
    int T,i,n,t;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(l,0,n*sizeof(int));
        memset(r,0,n*sizeof(int));
        for(i=0;i=0 && a[t]>=a[i])
            {
                t=l[t];
            }
            l[i]=t;
        }
        for(r[n-1]=INF,i=n-2;i>=0;i--)
        {
            t=i+1;
            while(t=a[i])
            {
                t=r[t];
            }
            r[i]=t;
        }
        for(i=0;i