首页 > 其他分享 >ACwing830 单调栈

ACwing830 单调栈

时间:2024-04-07 17:16:24浏览次数:21  
标签:ch ACwing830 top printf include 单调 define

这道题是

P8600 [蓝桥杯 2013 省 B] 连号区间数

的前置知识

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#define R(x) x = read()
#define For(i, j, n) for(int i = j ; i <= n ; ++i)
using namespace std;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
       x = x * 10 + ch - '0';
       ch = getchar();
    }
     return x * f;
}

const int N = 1e5 + 5;
int n, a[N];
int top, stk[N];

int main()
{
    R(n);
    for(int i = 1; i <= n; i++)
        R(a[i]);
    for(int i = 1; i <= n; i++)
    {
        while(top && stk[top] >= a[i])
            top--;
        if(!top) printf("-1 ");
        else printf("%d ", stk[top]);
        stk[++top] = a[i];
    }
    return 0;
}

 

标签:ch,ACwing830,top,printf,include,单调,define
From: https://www.cnblogs.com/smartljy/p/18119422

相关文章

  • 二分+单调队列优化 2
    7-7列车调度(天梯赛选拔赛)https://pintia.cn/problem-sets/1768624240956489728/exam/problems/1768624240990044166?type=7&page=0火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口(Entrance)轨道和一条出口(Exit)轨道,它们之间有N条平行的轨道。每趟列车从入口可以......
  • 二分+单调队列思想
    [AHOI2018初中组]分组(洛谷P4447)题目描述小可可的学校信息组总共有\(n\)个队员,每个人都有一个实力值\(a_i\)。现在,一年一度的编程大赛就要到了,小可可的学校获得了若干个参赛名额,教练决定把学校信息组的\(n\)个队员分成若干个小组去参加这场比赛。但是每个队员都不会愿意与......
  • 单调栈 and 单调队列学习笔记
    单调栈and单调队列学习笔记本文均以维护单调递增的栈/队列举例。本篇代码合集以后在写动态规划单调队列/单调栈优化的时候,这两个东西会合并。单调栈本质上就是模拟。假设要维护一个单调递增的栈,那么对于一个元素进来了,在栈顶的所有比他小的数我全部都要踢出去,不然就不满足......
  • 单调栈
    依据单调栈具有贼有趣的实现方式:在查找的同时,删除多余的,插入新的那么删除插入的过程和依据呢?我是nums[i],以找出左边第一个比我小的元素为例:栈里的元素是非降序的,而且都在我左边凡是栈里比我大的数(记为big),对找出左边第一个比我小的数来说,无效,可删对我右边的数来说,big也是对......
  • QMIX:用于深度多智能体强化学习的单调值函数分解
    目录QMIX:MonotonicValueFunctionFactorisationfor DeepMulti-AgentReinforcementLearningQMIX:用于深度多智能体强化学习的单调值函数分解Abstract 摘要1Introduction引言2RelatedWork 2相关工作3Background 3背景 3.1Deep Q-Learning 3.1深......
  • 蓝桥杯算法集训 - Week 4:BFS、并查集、Flood Fill、哈希、单调栈/队列
    蓝桥杯算法集训-Week4本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。一、BFSBFS算法复习参考:BFS(Java)广度优先搜索简单介绍、模板、案例(一)Ⅰ、代码模板staticvoidbfs(Troot){//双端队列,用来存储元素D......
  • 【模板】单调队列 滑动窗口最值
    LuoguP1886滑动队列/单调队列有一个长为 n 的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。 以求最小值为例f[i]表示以i结尾的窗口中的最小值f[i]=min(a[j]),i-k+1<=j<=i暴力算法O(n^2)......
  • 单调栈的妙用
    单调栈的妙用题目1题目链接402.移掉K位数字-力扣(LeetCode)题目大意给你一个以字符串表示的非负整数num和一个整数k,移除这个数中的k位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。示例输入:num="1432219",k=3输出:"1219"解释:移除掉三个数......
  • 单调队列 维护区间最值(板子+两道练手)
    1.P1886滑动窗口/【模板】单调队列https://www.luogu.com.cn/problem/P1886板子题,传送门在上方//Problem://P1886滑动窗口/【模板】单调队列////Contest:Luogu//URL:https://www.luogu.com.cn/problem/P1886//MemoryLimit:500MB//TimeLimit:1......
  • 数据结构(三)单调栈---以题为例
    给定一个长度为 N 的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出 −1。输入格式第一行包含整数 N,表示数列长度。第二行包含 N 个整数,表示整数数列。输出格式共一行,包含 N 个整数,其中第 i 个数表示第 i 个数的左边第一个比它小的数,如果不存在则输出......