D1. Range Sorting (Easy Version)(单调栈+思维)

简介: D1. Range Sorting (Easy Version)(单调栈+思维)

题目

题意

  • 给一个整数n和一个数组a[1~n]
  • 一次次排序操作的代价是,r - l
  • 求把所有子数组,排成有序的最小代价和

思路

easy版本可以用O(n2n^2n2)的算法,我们可以枚举左右端点

假设一段的最优排序方法如图

任意长度的一段序列排序可能是排序多个子序列

所以我们需要讨论加上一个点的情况

  1. 一号点比之前所有点大,所以不需要排序
  2. 二号点在第二段中间,所以需要和第二段放在一起排序,代价+1
  3. 三号点和第二段一起排序,代价+1,同上一情况
  4. 观察可以发现,把四号点排序需要和第一段和第二段一起排序,相当于合并了这两个段,代价合并段的长度+1
  5. 同上一步情况

讨论出了所有的情况,就可以发现这个思路类似单调栈

找到第一个段上最大值小于当前添加值的段,然后合并(弹出后操作,再返回栈中)

但是需要注意的是,这个单调栈维护的是一个段的信息,即段中的最大值

所以在栈中放入,每个段中的最大值,还要用已有的最大值来更新,之后放入的最大值

代码

cpp

复制代码

int a[N];
int n;
void solve()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)cin >> a[i];
    int ans = 0;
    for(int i = 1;i <= n;i ++)
    {
        stack<int> sta;
        for(int j = i;j <= n;j ++)
        {
            int cur = a[j];
            while(sta.size() && sta.top() > a[j])
            {
                cur = max(cur,sta.top());
                sta.pop();
            }
            sta.push(cur);
            ans += j - i + 1 - sta.size();
        }
    }
    cout << ans << endl;
}
相关文章
|
6天前
|
存储 前端开发 DataX
【数据结构】栈和队列
数据结构中的栈和队列
12 1
【数据结构】栈和队列
|
6天前
【数据结构OJ题】用栈实现队列
力扣题目——用栈实现队列
14 0
【数据结构OJ题】用栈实现队列
|
6天前
【数据结构OJ题】用队列实现栈
力扣题目——用队列实现栈
17 0
【数据结构OJ题】用队列实现栈
|
12天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
15 1
|
24天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
20天前
|
API
用栈翻转字符串
用栈翻转字符串
15 0
|
20天前
|
JavaScript
数据结构(用 JS 实现栈和队列【三种方式】)
数据结构(用 JS 实现栈和队列【三种方式】)
19 0
|
23天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
24天前
|
算法
数据结构与算法:栈与队列
数据结构与算法:栈与队列
|
27天前
|
存储 算法 调度
算法与数据结构-栈篇
算法与数据结构-栈篇
20 0