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

· · 题解

贪心，代码实现仅用数组，非常易懂且好写，而且跑得挺快的，赛时最优解第七，70ms。

题目传送门

可能更孬的阅读体验

题意简析

给定一个长度为 n 的序列，对其进行 n-1 次操作，每次操作都是下面两种中的一种，每次操作过后序列长度都自动减 1。

操作一：对于 1 \le i < l，将 a_{i} 更新为 \max(a_{i},a_{i+1})。

操作二：对于 1 \le i < l，将 a_{i} 更新为 \min(a_{i},a_{i+1})。

你最多可以进行 m 次操作一。

明显经过 n-1 次操作后序列长度将仅剩一个元素，求这个元素的最大值。

思路

我们来考虑一下操作一和操作二对答案的贡献。

很显然，因为我们想要让结果最大，当进行一次操作一或进行一次操作二时，操作一更优。

而当操作一和操作二都需要进行，这时我们考虑操作顺序对答案的影响。

设现在序列里有三个元素 a,b,c

对这个序列进行一次操作一和一次操作二

先进行操作一时答案为 \min(\max(a,b),\max(b,c))=\max(b,\min(a,c))

先进行操作二时答案为 \max(\min(a,b),\min(b,c))=\min(b,\max(a,c))

容易证明 \max(b,\min(a,c)) \ge \min(b,\max(a,c))，因为前者在最劣情况下会取到 (a,b,c) 中的中间值，最优情况下可以取到最大值，而后者最优情况下也只能取到中间值，最劣情况下会取到最小值

将三个数的情况推广，就可以得到贪心策略了：如果当前还可以进行操作一，先进行操作一必定优于先进行操作二。所以我们先把 m 次操作一全部做完，再做操作二就 OK 了。

下面是关于代码实现的一些细节

  1. 当做完 m 次操作一后，接下来的 n-1-m 次操作二实际上就是将现在的序列不断 \min，最终留下来的会是现在序列里的最小值。

  2. 我们想要将 m 次操作一的更新一遍完成，我们可以在当前到达 a_{i} 时用 a_{j}(i < j \le i+m) 更新 a_{i} 最大值，就不用一次一次挪了。

  3. 发现如果真按照上面的 2 这样去更新的话时间复杂度是 O(n \times m) 级的，所以需要优化一下。想一想什么时候 a_{j} 才会被用来更新 a_{i} 呢？只有当 a_{j} 比 a_{i} 到 a_{j} 间任意一个数都要大的时候才会用 a_{j} 更新 a_{j}，否则我们可以用这个更大数。因此我们改变一下写法，枚举 j，更新它前面 a_{i}(j-m \le i < j ) 的最大值，如果碰到一个中间的数不小于 a_{j}，继续往前更新了也是白更新，这里就可以直接 break 了。

  4. 木有了，开始愉快地写代码吧。

极简，不压，15 行 AC code：

（180ms，加入快读 70ms）

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000010],ans=0x3f3f3f3f;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans=max(ans,a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i-1;j>=1&&j>=i-m;j--){
            if(a[i]<=a[j])break;
            a[j]=a[i];
        }
    for(int i=1;i<=n-m;i++)ans=min(ans,a[i]);
    cout<<ans;
    return 0;
}