BZOJ4167 : 永远的竹笋采摘
永远
2023-09-11 14:15:04 时间
首先枚举出所有可能成为区间最小差值的点对$(j,i)$。
枚举每个位置作为右端点$i$,假设$a[j]>a[i]$。
找到第一个这样的$j$,那么可以将下一个$a[j]$的范围缩小到$(a[i],\frac{a[i]+a[j]}{2})$。这是因为在这之外的数要么没有$j$优,要么会被$j$考虑到。
利用可持久化线段树可以很容易地找到下一个$j$的位置,最多$O(n\log n)$个点对,时间复杂度$O(n\log^2n)$。
接下来的问题等价于选择$k$条不相交线段,使得价值和最小。
将线段按左端点从小到大排序,设$f[i][j]$表示考虑前$i$条线段,选择了$j$条线段的最优价值,可以通过双指针优化到$O(kn\log n)$。
注意到$f[all][j]$是个凸函数,故可以二分斜率$mid$来切它,具体体现为每选一条线段,价值就多加$mid$。
那么随着$mid$的增大,最优解中选择的线段数目会越来越少。
二分找到最优解中线段数目最接近$k$的$mid$即可。
时间复杂度$O(n\log^2n)$。
#include<cstdio> #include<algorithm> using namespace std; const int N=50010,M=N*18; int n,m,K,i,a[N],tot,T[N],l[M],r[M],v[M],tmp,ans,s[N],g[M*2];double L,R,MID,f[M*2]; struct E{int l,r,v;E(){}E(int _l,int _r,int _v){l=_l,r=_r,v=_v;}}e[M*2]; inline bool cmp(const E&a,const E&b){return a.l<b.l;} inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} int ins(int x,int a,int b,int c,int p){ int y=++tot; v[y]=p; if(a==b)return y; int mid=(a+b)>>1; if(c<=mid)l[y]=ins(l[x],a,mid,c,p),r[y]=r[x]; else l[y]=l[x],r[y]=ins(r[x],mid+1,b,c,p); return y; } void ask(int x,int a,int b,int c,int d){ if(!x)return; if(c<=a&&b<=d){ if(v[x]>tmp)tmp=v[x]; return; } int mid=(a+b)>>1; if(c<=mid)ask(l[x],a,mid,c,d); if(d>mid)ask(r[x],mid+1,b,c,d); } inline void findbigger(int x){ int l=a[x]+1,r=n,t=x-1; while(l<=r&&t){ tmp=0; ask(T[t],1,n,l,r); if(!tmp)return; t=tmp; e[++m]=E(t,x,a[t]-a[x]); r=(a[x]+a[t--]-1)>>1; } } inline void findsmaller(int x){ int l=1,r=a[x]-1,t=x-1; while(l<=r&&t){ tmp=0; ask(T[t],1,n,l,r); if(!tmp)return; t=tmp; e[++m]=E(t,x,a[x]-a[t]); l=(a[x]+a[t--]+2)>>1; } } inline void up(int&x,int y){if(f[x]>f[y])x=y;} inline void cal(){ int i,j; for(i=1;i<=n;i++)s[i]=0; for(i=1,j=ans=0;i<=m;i++){ while(j+1<e[i].l){ j++; up(s[j],s[j-1]); } f[i]=f[s[j]]+e[i].v+MID; g[i]=g[s[j]]+1; up(s[e[i].r],i); up(ans,i); } } int main(){ read(n),read(K); for(i=1;i<=n;i++)read(a[i]),T[i]=ins(T[i-1],1,n,a[i],i); for(i=1;i<=n;i++)findbigger(i),findsmaller(i); sort(e+1,e+m+1,cmp); L=-1e9,R=1e9; for(int _=80;_;_--){ MID=(L+R)/2; cal(); if(g[ans]==K)break; if(g[ans]<K)R=MID;else L=MID; } return printf("%.0f",f[ans]-MID*K),0; }
相关文章
- 《惢客创业日记》2019.05.03(周五)永远匿名的红颜知己(一)
- 【BZOJ4167】永远的竹笋采摘 分块+树状数组
- 山石网科杨庆华:边界防御已死?网络安全永远需要防护叠加而非取代
- 永远不要在Linux执行的10个最危险的命令
- 终生学习者,永远劳苦命!
- 书,永远的朋友
- Android下写一个永远不会被KILL掉的进程/服务
- Qt之美(一):d指针/p指针详解(解释二进制兼容,以及没有D指针就会崩溃的例子。有了D指针,所使用的对象大小永远不会改变,它就是该指针的大小。这个指针就被称作D指针)good
- 被动永远做不好运维
- 远离“数据呆” 对业务的理解和思考永远高于分析技术的选择
- 如何让微信丢骰子永远只出“666”