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

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