Hello 2024

Grouping Increases

题目

输入长度为 \(n\) 的数组 \(a\)，将数组 \(a\) 分割为两个子序列（可能为空），输出两个子序列中满足 \(b_{i}<b_{i+1}\) 的下标 \(i\) 的数量之和的最小值。

数据范围：\(1\leq n\leq 2\times 10^{5}\)，\(1\leq a_{i}\leq n\)。

思路

贪心。假设将数组 \(a\) 分割为数组 \(b\) 和 \(c\)，从空数组开始，将 \(a\) 中的元素添加到 \(b\) 或 \(c\)。假设 \(b\) 和 \(c\) 的最后一个元素分别为 \(x\) 和 \(y\)（\(x\leq y\)），如果 \(a_{i}\leq x\) 或 \(a_{i}>y\)，则将 \(a_{i}\) 添加到 \(b\)，否则添加到 \(c\)。