自动搬运

查看原文

来自洛谷，原作者为

	Rannio 学术开着 || 无 √7 不改签

搬运于2025-08-24 23:02:06，当前版本为作者最后更新于2024-08-17 11:58:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先说结论：先把操作一用完是最优的。

证明：

每次操作一都是在 $a_i$ 与 $a_{i+1}$ 中取最大值，做 $x-1$ 次取最大值操作就相当于删去一个最小值，取出前 $x-1$ 大的值。容易发现这样会使最小值变大。

而做一次操作二就相当于删去一个最大值，取出前 $x-1$ 小的值。做 $x-1$ 次操作二就相当于取出原数组最小值，那么此时使最小值最大一定是最优的。

此时我们回过来看做 $m$ 次操作的影响，容易发现做 $m$ 次在 $a_i$ 与 $a_{i+1}$ 中取最大值的操作就相当于删去 $a_i$ 至 $a_{i+m}$ 的 $m-1$ 个最小值，取出最大值，而此时再做 $n-m$ 次操作二就是在做完 $m$ 次操作一的数组中取最小值，这个就是答案。

区间最值用线段树维护即可，时间复杂度 $\mathcal{O}(n \log n)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans=LLONG_MAX;
int a[1000005],b[1000005];
struct node{
	int l,r,sum1;
}tree[4000005];
void upd(int now){
    tree[now].sum1=max(tree[now<<1].sum1,tree[now<<1|1].sum1);
}
void build(int now,int l,int r){
    tree[now].l=l;
	tree[now].r=r;
	if(l==r){
        tree[now].sum1=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	upd(now);
}
int search1(int now,int l,int r){
	if(tree[now].l>=l&&tree[now].r<=r) return tree[now].sum1;
	int mid=(tree[now].l+tree[now].r)>>1;
	if(r<=mid) return search1(now<<1,l,r);
	else if(l>mid) return search1(now<<1|1,l,r);
	else return max(search1(now<<1,l,mid),search1(now<<1|1,mid+1,r));
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=1;i<=n-m;i++){
        b[i]=search1(1,i,i+m);
        ans=min(ans,b[i]);
    }
    printf("%lld",ans);
    return 0;
}