hdu3410 Passing the Message

本文主要是介绍hdu3410 Passing the Message，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接:hdu3410
题目大意:
T组数据
输入n个人的身高(n<=50000),身高各不相同.
输出每个人左右各比他矮的人中最高的那个.

题解:
单调队列
从左往右从右往左各一次

如果hyc来了别看…
我在刷水题qwq我好菜啊.jpg

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 51000int mymin(int x,int y) {return (x<y)?x:y;}
int mymax(int x,int y) {return (x>y)?x:y;}
int a[maxn],l[maxn],r[maxn],q[maxn],cnt;
int main()
{int T,i,n,tp;scanf("%d",&T);for (int ca=1;ca<=T;ca++){scanf("%d",&n);for (i=1;i<=n;i++){scanf("%d",&a[i]);l[i]=r[i]=q[i]=0;}tp=0;for (i=1;i<=n;i++){while (tp>0 && a[i]>a[q[tp]]) {l[i]=(a[l[i]]>a[q[tp]])?l[i]:q[tp];tp--;}q[++tp]=i;}tp=0;for (i=n;i>=1;i--){while (tp>0 && a[i]>a[q[tp]]) {r[i]=(a[r[i]]>a[q[tp]])?r[i]:q[tp];tp--;}q[++tp]=i;}printf("Case %d:\n",ca);for (i=1;i<=n;i++)printf("%d %d\n",l[i],r[i]);}return 0;
}

这篇关于hdu3410 Passing the Message的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---