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;
}