本节为思维上的基本功，算法较杂。

例题英雄辈出

题目描述

给你一个排列，你需要输出每个元素后第一个比其大的元素下标，若不存在输出

-1

。

思路形成

序列转为二维平面点。
上下左右，四个方向，每个方向还能有多解。

序列问题，先用三个特殊序列过脑子：

升序
降序
全部相同的序列

上

从大到小考虑每个元素。
Hint: 可以使用 set 等

下

从小到大考虑每个元素。
Hint: 每次删除最小元素

左

从左到右考虑每个元素
Hint: 单调栈存问题

右

从右到左考虑每个元素
Hint: 单调栈存答案

请着重思考你的单调栈存了什么。
选出你认为的最佳解法把~

例题 UFO

题目描述

给你若干个区间，每个区间都有个权值。
问对于每个位置，所有覆盖该位置的区间权值最小是多少？

理解

想一想图像，这里区间的高度较为明显。

思路形成

上

从高到低考虑每个区间

下

从低到高考虑每个区间

左

从左到右考虑每个元素
Hint: 扫描线 + set 存储

右

与左有对称性

例题 Sequence 序列问题

\boxed{\text{上下左右的思维方法}}

上

元素从大到小
Hint: 想象一个山峰，最大值必须留到最后。

下

元素从小到大
Hint: 山谷合并旁边

左

元素从左到右
Hint1: 思考形如 $6,5,4,3,2,1$ 的单调序列
Hint2: 思考形如 $3,1,2$ 简单乱序序列
Hint3: 单调栈

右

与左有对称性

正解

可以由上面任意一种再思考一下得到。

CPP

long long ans=0;
for(int i=1;i<n;i++)
    ans+=max(a[i],a[i+1]);
cout<<ans;

例题挂缀 pendant

题目大意

选择最好的解法，不要局限于单一解法。
本题有三维信息，但显然珠缀的编号是无效的。
所以只有两维（区间级别）

问题转化

已知每一个区间左端点最右能在哪，以及区间长度，求能选几个不重叠的区间。

按照右端点限制排序

模拟，贪心，反悔

按照区间排序

线段树 + 基本功。
十分复杂。

一题多解复习

文章操作

例题英雄辈出

题目描述

思路形成

上

下

左

右

例题 UFO

题目描述

理解

思路形成

上

下

左

右

例题 Sequence 序列问题

上

下

左

右

正解

例题挂缀 pendant

题目大意

问题转化

按照右端点限制排序

按照区间排序

相关推荐

评论

一题多解复习

文章操作

例题 英雄辈出

题目描述

思路形成

上

下

左

右

例题 UFO

题目描述

理解

思路形成

上

下

左

右

例题 Sequence 序列问题

上

下

左

右

正解

例题 挂缀 pendant

题目大意

问题转化

按照右端点限制排序

按照区间排序

相关推荐

评论

例题英雄辈出

例题挂缀 pendant