P10878 [JRKSJ R9] 在相思树下 III 题解

本文主要是介绍P10878 [JRKSJ R9] 在相思树下 III 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定一个长为 $n$ 的序列 $a_{1\dots n}$ ，需要对它进行两种操作共 $n - 1$ 次。

对一个长度为 $l$ 的序列 $b_{1\dots l}$ 进行一次操作将会把序列变为一个长为 $l - 1$ 的序列 $c_{1\dots l-1}$ ：

操作一中， $\forall i\in[1,l),c_i=\max(b_i,b_{i+1})$ ；
操作二中， $\forall i\in[1,l),c_i=\min(b_i,b_{i+1})$ 。

给定整数 $m$ ，你只能进行至多 $m$ 次操作一。进行 $n - 1$ 次操作后序列 $a$ 的长度变为 $1$ 。你可以任意安排操作的顺序，求最终剩余的数 $a_1$ 的最大值。

Solution

比第一题简单。

两个关键性质就是操作一做满 $m$ 次最优，且做完操作一再做操作二。

我们发现操作一每次一定会把当前最小值消去，使最大值数量变多，操作二一定会把当前最大值消去，使最小值数量变多。

先做操作一则能抬高数值下限，做满 $m$ 次使最小值最大，最大值数量最多，此种决策最优。

而在一次操作一前做操作二，不仅会使最小值变多，还会降低数值上限，不优于上种决策。

确定了操作顺序后就完了吗？并不是，还需要找到最小值，而直接模拟是 $O(n^2)$ 的。

发现在一次操作一后可能不止最小值会消去，如 $[1, 3, 2, 3]$ 做一次操作一变成 $[3, 3, 3]$ 。

又发现一个数会被左右两边第一个比它大的数 $a_l,a_r$ 消去，会在 $r - 1 - l$ 次操作一后消失。

然后在在所有不能在 $m$ 次操作一之内消去的数中取最小值即可。

用单调栈找 $a_l,a_r$ 可 $O (n)$ 做完。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000010];
int l[1000010],r[1000010];
stack<int> s;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){while(s.size()&&a[s.top()]<=a[i]){s.pop();}l[i]=s.size()?s.top():0;s.push(i);}while(s.size()) s.pop();for(int i=n;i>=1;i--){while(s.size()&&a[s.top()]<=a[i]){s.pop();}r[i]=s.size()?s.top():n+1;s.push(i);}int minn=1e9;for(int i=1;i<=n;i++){if(r[i]-1-l[i]>m){minn=min(minn,a[i]);}}cout<<minn;return 0;
}