Passing the Message-蒲公英云

Passing the Message

![Image 1][]

![Image 1][]![Image 1][]

![Image 1][]

![Image 1][]![Image 1][]

题意：传信息，左边传给比自己矮的人中最高的那个，右边也是如此，输出每个人左右的被传递者，若左右没有比自己矮的人，输出0.

思路：维护一个从大到小的单调栈，最后一个被pop掉的元素是最大的。

#include<stdio.h>
#include<stack>
#include<memory>
using namespace std;
#define maxn 50010
#define ll  long long
ll  a[maxn];
ll l[maxn], r[maxn];
stack<ll>s1, s2;
int main(){
    int N, T, cnt=0;
    scanf("%d", &T);
    while(T--)
    {
        memset(l, 0, sizeof(l));//每一次案例须重新初始化的必须重新初始化。
        memset(r, 0, sizeof(r));
        while(!s1.empty())s1.pop();
        while(!s2.empty())s2.pop();
        scanf("%d", &N);
        for(int i=1; i<=N; i++)
        {
            scanf("%lld", a+i);
        }
        for(int i=1; i<=N; i++)//左边。
        {
            while(!s1.empty() && a[i]>a[s1.top()])
            {
                l[i]=s1.top();//其实只有最后一次有用。        
                s1.pop();
            }
            s1.push(i);
        }
        for(int i=N; i>=1; i--)//右边。
        {
            while(!s2.empty() && a[i]>a[s2.top()]) 
            {
                r[i]=s2.top();
                s2.pop();
            }
            s2.push(i);
        }
        printf("Case %d:\n", ++cnt);
        for(int i=1; i<=N; i++)
        {
            printf("%lld %lld\n", l[i], r[i]);
        }
    }
    return 0;
}