Passing the Message-HDU3410

题目链接: [](Problem - 3410 (hdu.edu.cn))

小难啊这题....

$2^8$

题目大意：

输出每一个位置的人向左/右看，看到的比他矮的最高的人的下标。（每个同学的身高不一样）如果有人比他高那就看不到那个比他高的人后面了（视野会被挡住）

思路：

只要解决向右看，向左看就迎刃而解了，只是方向不一样。

对于每一个位置i，只记录[i+1,n]中的最大值是不够的，因为很有可能最大值所在位置和i之间有符合比i矮的最大的这一条件位置。

需要维护一个栈顶到栈底递增的单调栈来记录i后面的情况。举个例子，如果i位后是4 3 5，这个3是多余的，因为i位无非两种情况：1. i<=4 那么i根本看不到3；2. i>4 那么i虽然可以看到3，但是找最大值是轮不到这个3的（有4，5在）

例子：

因为向右边看要得出准确答案需要右边的区间提前处理完毕，所以向右边看就是从后往前遍历，反之则从前往后遍历。

总的来说，要维护一个范围为[i+1,n]的单调栈（栈顶到栈低单调递增），供i往后面找符合条件的值，并且在找的过程中，通过弹栈保持单调性。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define drep(i,a,b) for(int i=b;i>=a;i--)
using namespace std;
const int N = 5*1e5+50;
int T,n,cas;
struct kid{
	int h,idx;
}a[N];
int ansl[N],ansr[N];

void solve(){
	stack<kid>st;
	drep(i,1,n){
		while(st.size() && st.top().h<=a[i].h){
			if(st.top().h != a[i].h)ansr[i]=st.top().idx;
			st.pop();
		}st.push(a[i]);
	}
	stack<kid>sk;
	rep(i,1,n){
		while(sk.size() && sk.top().h<=a[i].h){
			if(sk.top().h != a[i].h)ansl[i]=sk.top().idx;
			sk.pop();
		}sk.push(a[i]);
	}
	printf("Case %d:\n",++cas);
	rep(i,1,n)printf("%d %d\n",ansl[i],ansr[i]);
	
	
}

int main(){
	scanf("%d",&T);
	while(T--){
		memset(ansr,0,sizeof ansr);
		memset(ansl,0,sizeof ansl);
		scanf("%d",&n);
		a[n+1].h=a[n+1].idx=0;
		rep(i,1,n){
			scanf("%d",&a[i].h);
			a[i].idx=i;
		}
		solve();
	}
}

Passing the Message