正題

題目鏈接:https://www.luogu.com.cn/problem/P3466

---

題目大意

$n$個數(shù)，每次可以讓一個$+1$或$?1$，要求操作次數(shù)最少使得有連續(xù)$k$個相同的。

---

解題思路

枚舉是哪$k$個，然后用平衡樹（或?qū)敹?#xff09;維護中位數(shù)和比中位數(shù)小的值，這里平衡樹寫的少就直接用$Treap$維護了。

時間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #define ll long long using namespace std; const ll N=1e5+10; ll n,k,tot,rt,a[N],dat[N],sum[N],siz[N],cnt[N],t[N][2],w[N]; void PushUp(ll x){sum[x]=sum[t[x][0]]+sum[t[x][1]]+w[x]*cnt[x];siz[x]=siz[t[x][0]]+siz[t[x][1]]+cnt[x];return; } void zig(ll &x){ll y=t[x][0];t[x][0]=t[y][1];t[y][1]=x;x=y;PushUp(t[y][1]);PushUp(y);return; } void zag(ll &x){ll y=t[x][1];t[x][1]=t[y][0];t[y][0]=x;x=y;PushUp(t[y][0]);PushUp(y);return; } void Insert(ll &x,ll val,ll k){if(!x){x=++tot;dat[x]=rand();w[x]=sum[x]=val;siz[x]=cnt[x]=1;return;}else if(val==w[x]){cnt[x]+=k;PushUp(x);return;}if(val<w[x]){Insert(t[x][0],val,k);if(dat[x]>dat[t[x][0]])zig(x);}else{Insert(t[x][1],val,k);if(dat[x]>dat[t[x][1]])zag(x);}PushUp(x);return; } ll GetVal(ll x,ll k,ll &S){if(k<=siz[t[x][0]])return GetVal(t[x][0],k,S);S+=sum[x]-sum[t[x][1]];if(k<=siz[x]-siz[t[x][1]]){int z=siz[x]-siz[t[x][1]]-k;S-=w[x]*z;return w[x];}return GetVal(t[x][1],k-siz[x]+siz[t[x][1]],S); } int main() {srand(19260817);scanf("%lld%lld",&n,&k);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);ll z=0,mark1=0,mark2=0,ans=1e18;for(ll i=1;i<k;i++)Insert(rt,a[i],1),z+=a[i];for(ll i=k;i<=n;i++){Insert(rt,a[i],1);z+=a[i];ll S=0,val=GetVal(rt,k-k/2,S);S=(z-S)-k/2*val+(k-k/2)*val-S;if(ans>S)ans=S,mark1=i,mark2=val;Insert(rt,a[i-k+1],-1);z-=a[i-k+1];}printf("%lld\n",ans);for(ll i=1;i<=n;i++){if(i>mark1-k&&i<=mark1)printf("%lld\n",mark2);else printf("%lld\n",a[i]);}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的P3466-[POI2008]KLO-Building blocks【Treap】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。