Passing the Message

╰+攻爆jí腚メ 2022-06-12 12:07 205阅读 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 条评论，205人围观）

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

相关阅读

相关 Java多线程通信机制：Message Passing Case Study

在Java多线程通信中，Message Passing（消息传递）是一种常见的沟通方式。下面我们将通过一个案例来详细理解Java多线程通信中的Message Passing。

Love The Way You Lie/ 2024年10月10日 07:30/ 0 赞/ 31 阅读

相关 The passé composé tense in FRENCH

passé composé utilisation du passé composé passé composé raconter un fait dans

ゞ浴缸里的玫瑰/ 2024年02月19日 09:17/ 0 赞/ 37 阅读

相关 pass

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

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

相关 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 赞/ 125 阅读

相关 Lotus Miner the message pool 消息池

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

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

相关 MQTT: The Standard for IoT Messaging

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

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

相关 upload(Pass-10~Pass-)

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

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

相关 upload(pass01~pass09)

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

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

相关 Passing the Message

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

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

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

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

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