Passing the Message

╰+攻爆jí腚メ 2022-06-12 12:07 133阅读 0赞

![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;
    }

本人语拙，如有不懂，尽请留言，如有不足，不吝赐教。

[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关 pass

在linux服务器nginx环境下rewrite规则怎么写一．正则表达式匹配，其中： \~为区分大小写匹配 \~\为不区分大小写匹配 \!~和!~\分别为区分大小

ゝ一世哀愁。/ 2023年09月25日 09:06/ 0 赞/ 12 阅读

相关 LeetCode（String) 2325. Decode the Message

1.问题 You are given the strings key and message, which represent a cipher key and a se

àì夳堔傛蜴生んèń/ 2023年09月23日 21:57/ 0 赞/ 90 阅读

相关 failed to unmarshal the received message proto问题排查

前言突然发现已经有很久没有登录过csdn了，工作后一直很忙，没有什么时间来写博客，平日学习、踩坑往往都是自己简单记录一下，但实际上经常写博客还是有必要的，一方面可以加深

Bertha 。/ 2023年01月15日 14:30/ 0 赞/ 133 阅读

相关 Lotus Miner the message pool 消息池

Lotus Miner the message pool 消息池 1，等待上链消息 2，查看基础手续费\`Base Fee\` 3，查看链上消息费用

深藏阁楼爱情的钟/ 2022年12月21日 09:26/ 0 赞/ 68 阅读

相关 MQTT: The Standard for IoT Messaging

今天开始集中火力, 猛攻MQTT, 争取一个月内上线新功能. 1. 读了官方文档, 才知道MQTT并不是什么Message Queue Telemetry Transpor

淡淡的烟草味﹌/ 2022年10月29日 12:22/ 0 赞/ 157 阅读

相关 upload(Pass-10~Pass-)

文章目录 Pass-10 Pass-11 Pass-12（失败） Pass-10 查看提示：`本pass只允许上传.jpg|.png|.gif后

拼搏现实的明天。/ 2022年09月12日 15:53/ 0 赞/ 146 阅读

相关 upload(pass01~pass09)

文章目录 Pass-01 Pass-02 Pass-03 Pass-04（未解决） Pass-05（失败）自己的一些尝试：

我会带着你远行/ 2022年09月12日 13:56/ 0 赞/ 141 阅读

相关 Passing the Message

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

╰+攻爆jí腚メ/ 2022年06月12日 12:07/ 0 赞/ 134 阅读

相关 Passing Objects

All PeopleCode objects can be passed as function parameters. You can pass complex data s

今天药忘吃喽~/ 2021年11月13日 18:30/ 0 赞/ 165 阅读

相关 "Ray, Pass me the dishes!" UVALive - 3938 （线段树）

题意：给出询问a,b求出a，b区段内的最大子串思路：不难想象，一个区段的最大子串要么为其两个子区段的最大子串，要么第一个子串的最大后缀加上第二个子串的最大前缀。因...

灰太狼/ 2021年03月28日 14:42/ 0 赞/ 316 阅读