题解：P12372 [蓝桥杯 2022 省 Python B] 最优清零方案

· · 题解

蓝桥杯2022省赛PythonB组 - 最优清零方案 题解

题目描述

给定长度为 N 的数列，每次操作可选择：

  1. 单点减 1 （操作代价1）
  2. 连续 K 个数各减 1 （操作代价1）

求将整个数列清零的最少操作次数。

思路

因为 K \ge 1 所以多用操作 2 更优。

对于每个长度为 K 的区间，都用操作 2 操作这个区间所有的数的最小值次（用线段树维护）。

最后再将操作后剩下的所有数加起来就行了。

Code


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int a[N];
struct node{
    int ls,rs,sum,add,mx,mn;
    #define l(x) tr[x].ls
    #define r(x) tr[x].rs
    #define mn(x) tr[x].mn
    #define mx(x) tr[x].mx
    #define sum(x) tr[x].sum
    #define add(x) tr[x].add
}tr[N*4];
void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    if(l==r){
        sum(p)=a[l];
        mn(p)=mx(p)=a[l];
        return; 
    } 
    int mid=l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=sum(p*2)+sum(p*2+1);
    mn(p)=min(mn(p*2),mn(p*2+1));
    mx(p)=max(mx(p*2),mx(p*2+1));
}
void spread(int p){
    if(add(p)){
        sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
        mx(p*2)+=add(p),mn(p*2)+=add(p); 
        add(p*2)+=add(p);
        sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
        mx(p*2+1)+=add(p),mn(p*2+1)+=add(p); 
        add(p*2+1)+=add(p);
        add(p)=0;
    }
}
void change(int p,int l,int r,int d){
    if(l(p)>=l && r(p)<=r){
        sum(p)+=(r(p)-l(p)+1)*d;
        add(p)+=d;
        mn(p)+=d,mx(p)+=d;
        return;
    }
    int mid=l(p)+r(p)>>1;
    spread(p);
    if(l<=mid) change(p*2,l,r,d);
    if(r>mid)  change(p*2+1,l,r,d);
    sum(p)=sum(p*2)+sum(p*2+1);
    mn(p)=min(mn(p*2),mn(p*2+1));
    mx(p)=max(mx(p*2),mx(p*2+1));
}
int ask(int p,int l,int r){
    if(l(p)>=l && r(p)<=r){
        return mn(p);
    }
    spread(p);
    int mid=l(p)+r(p)>>1;
    int ans=2e9;
    if(l<=mid) ans=min(ans,ask(p*2,l,r));
    if(r>mid)  ans=min(ans,ask(p*2+1,l,r));
    return ans;
}
int ask2(int p,int l,int r){
    if(l(p)>=l && r(p)<=r){
        return sum(p);
    }
    spread(p);
    int mid=l(p)+r(p)>>1;
    int ans=0;
    if(l<=mid) ans+=ask2(p*2,l,r);
    if(r>mid)  ans+=ask2(p*2+1,l,r);
    return ans;
}
int k,ans=0;
signed main(){
    int n,m;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=n-k+1;i++){
        int maxx=ask(1,i,i+k-1);
        ans+=maxx;
        if(maxx>0) change(1,i,i+k-1,-maxx); 
    }
    ans+=ask2(1,1,n);
    cout<<ans;
}