MT3039 山脉

简介: MT3039 山脉

6f2cd0b0d225444ea5de1ac3e27c4d4b.jpg

e1d03777e74848bca043a34db7884f67.jpg

思路:


往右看能看到山顶,可以看成找第一个比当前元素>=的元素,即构造单调递减栈。


例子:


7 5 3 4

1. 7入栈: 7

2. 5入栈: 7 5  ans=ans+1(1是指有1个元素(7)可以看到5)

3. 3入栈: 7 5 3 ans=ans+2(2是指有2个元素(7,5)可以看到3)

4. 3出栈4入栈: 7 5 4 ans=ans+2(2是指有2个元素(7,5)可以看到4)

所以最终ans=1+2+2=5


易错点:


开long long。

判断元素是否进栈需要判断 s.top() <= num,不要忘记等号。

使用 ios::sync_with_stdio(false);   cin.tie(0);  cout.tie(0);在C++中关闭输入输出流的同步,以提高程序的执行效率。

或者使用scanf和printf,避免超时


代码:


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6 + 10;
ll n;
stack<ll> s; // 单调栈
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    ll ans = 0;
    ll num;
    for (ll i = 1; i <= n; i++)
    {
        cin >> num;
        while (!s.empty() && s.top() <= num) // 栈顶<=要进来的元素:栈顶元素出栈
        {
            s.pop();
        }
        s.push(num);
        ans += s.size() - 1;
    }
    cout << ans;
    return 0;
}


或者使用scanf和printf

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6 + 10;
ll n;
stack<ll> s; // 单调栈
int main()
{
    scanf("%d", &n);
    ll ans = 0;
    ll num;
    for (ll i = 1; i <= n; i++)
    {
        scanf("%d", &num);
        while (!s.empty() && s.top() <= num) // 栈顶<=要进来的元素:栈顶元素出栈
        {
            s.pop();
        }
        s.push(num);
        ans += s.size() - 1;
    }
    printf("%d", ans);
    return 0;
}


相关文章
|
11月前
|
弹性计算 API 云计算
使用LobeChat轻松打造私人智能聊天助手
阿里云计算巢提供了一键部署LobeChat的功能,无需下载代码或安装复杂依赖,通过简单几步即可搭建私人聊天助手,非常适合非技术人员。LobeChat是一款现代化设计的开源聊天应用,支持语音合成及多模态插件系统。部署前需确保已开通阿里云账号且余额充足。
使用LobeChat轻松打造私人智能聊天助手
|
11月前
|
数据可视化 Python
Matplotlib 教程 之 Seaborn 教程 10
Seaborn 是基于 Matplotlib 的 Python 数据可视化库,专注于统计图形的绘制。它提供了高级接口和美观的默认主题,简化了复杂图形的生成过程。Seaborn 支持多种图表类型,如散点图、折线图、柱状图、热图等,并特别强调视觉效果。例如,使用 `sns.violinplot()` 可以轻松绘制展示数据分布的小提琴图。
116 1
|
Oracle Java 数据库连接
实时计算 Flink版操作报错合集之在向协调器发送请求时出现报错,该如何解决
在使用实时计算Flink版过程中,可能会遇到各种错误,了解这些错误的原因及解决方法对于高效排错至关重要。针对具体问题,查看Flink的日志是关键,它们通常会提供更详细的错误信息和堆栈跟踪,有助于定位问题。此外,Flink社区文档和官方论坛也是寻求帮助的好去处。以下是一些常见的操作报错及其可能的原因与解决策略。
|
应用服务中间件 Linux Shell
【Shell脚本】Linux安装Nginx以及开机自启
【Shell脚本】Linux安装Nginx以及开机自启
【Shell脚本】Linux安装Nginx以及开机自启
|
监控 Linux 开发工具
工欲善其事,必先利其器-基于ubuntu18.04搭建100ASK-ESP32开发环境并成功点灯
工欲善其事,必先利其器-基于ubuntu18.04搭建100ASK-ESP32开发环境并成功点灯
260 0
|
消息中间件 算法 NoSQL
秋招上岸“我”都做对了哪些事?
秋招上岸“我”都做对了哪些事?
166 2
秋招上岸“我”都做对了哪些事?
|
人工智能 BI
【每日一题Day324】LC1462课程表 IV | BFS 拓扑排序 Floyd
【每日一题Day324】LC1462课程表 IV | BFS 拓扑排序 Floyd
59 0
|
测试技术 程序员 API
3个案例,详解如何选择合适的研发模式 | 研发效能提升36计
3个案例,详解如何选择合适的研发模式,研发模式的选择与产品形态、发布方式、团队规模、协作成熟度密切相关。本文我们将根据不同的团队场景,分析如何选择适合团队的研发模式。
1384 1
3个案例,详解如何选择合适的研发模式 | 研发效能提升36计
|
机器学习/深度学习 人工智能 算法
基础算法才是王道!谷歌2022年终总结第五弹:真正的「算法工程师」都在研究啥?
基础算法才是王道!谷歌2022年终总结第五弹:真正的「算法工程师」都在研究啥?
291 0
|
XML Java Android开发
SpringBoot入门:使用IDEA和Eclipse构建第一个SpringBoot项目
Spring Boot是一个简化Spring开发的框架,用来监护spring应用开发,约定大于配置,去繁就简,just run 就能创建一个独立的,产品级的应用。我们在使用Spring Boot时只需要配置相应的Spring Boot就可以用所有的Spring组件,简单的说,spring boot就是整合了很多优秀的框架,不用我们自己手动的去写一堆xml配置然后进行配置。所以springboot在java开发中也变得越来越重要,这里总结一下如何使用IDEA和Eclipse创建一个简单的springboot项目。
571 0
SpringBoot入门:使用IDEA和Eclipse构建第一个SpringBoot项目