本文主要是介绍(2019杭电多校3) Distribution of books (dp+离散化+线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
题意：n个数，可以选择前m(m自定)个数分成k块，问每块的数字和的最大值最小是多少
解：首先我们可以二分这个最小的最大值mid，然后去check，我们可以定义dp[i]，前i本书在满足<=mid的情况下最多可以分成几块，那么当sum[i]<=mid的情况下，dp[i]=1,反之0；更新的话dp[i]=max(dp[i],dp[i]+1) (当sum[i]-sum[j]<=mid的情况下)，这样是一个n^2的复杂度显然不行，我们就是想知道那些sum[j]>=sum[i]-mid的j中最大的dp[j]嘛，所以我们就建一颗权值线段树，最下面一层为sum[j],值就是dp[j],当然由于这里的sum会很大，所以需要离散化。然后dp[i]得出之后，再更新一下线段树即可。
#include<bits/stdc++.h>
#define il inline
#define pb push_back
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define SZ(a) int((a).size())
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int N=2e5+105;
template <typename _Tp> il void read(_Tp&x) {char ch;bool flag=0;x=0;while(ch=getchar(),!isdigit(ch)) if(ch=='-')flag=1;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();if(flag) x=-x;
}
//il int Add(ll &x,ll y) {return x=x+y>=mod?x+y-mod:x+y;}
//il int Mul(ll &x,ll y) {return x=x*y>=mod?x*y%mod:x*y;}
int T,n,k,a[N],sid[N],tr[N<<2],sz;
ll sum[N],s[N];
il void build(int l,int r,int rt){tr[rt]=0;if(l==r) return ;build(l,mid,rt<<1),build(mid+1,r,rt<<1|1);
}
il int query(int l,int r,int L,int R,int rt){if(L<=l && R>=r) return tr[rt];int ans=0;if(L<=mid) ans=max(ans,query(l,mid,L,R,rt<<1));if(R>mid) ans=max(ans,query(mid+1,r,L,R,rt<<1|1));return ans;
}
il void update(int l,int r,int x,int c,int rt){if(l==r){tr[rt]=max(tr[rt],c);return ;}if(x<=mid) update(l,mid,x,c,rt<<1);else update(mid+1,r,x,c,rt<<1|1);tr[rt]=max(tr[rt<<1],tr[rt<<1|1]);
}
int dp[N];//前i本书最多可以分给几个人(在区间和<=x的情况下
il bool ck(ll x){build(1,sz,1);for(int i=1;i<=n;++i) dp[i]=0;int pos,q,num=0;for(int i=1;i<=n;++i){if(sum[i]<=x) dp[i]=1;pos=lower_bound(s+1,s+sz+1,sum[i]-x)-s;q=query(1,sz,pos,sz,1);if(q!=0) dp[i]=max(dp[i],q+1);num=max(num,dp[i]);update(1,sz,sid[i],dp[i],1);}if(num>=k) return true; else return false;
}
int main(){
// std::ios::sync_with_stdio(0);cin.tie(0);read(T);while(T--){read(n),read(k);for(int i=1;i<=n;++i){read(a[i]),sum[i]=sum[i-1]+a[i],s[i]=sum[i];}sort(s+1,s+n+1);sz=unique(s+1,s+n+1)-(s+1);for(int i=1;i<=n;++i) sid[i]=lower_bound(s+1,s+sz+1,sum[i])-s;ll le=-1e18,ri=1e18,md,ans=1e18;while(le<=ri){md=(le+ri)>>1;if(ck(md)) ans=md,ri=md-1;else le=md+1; }printf("%lld\n",ans);}return 0;
}
这篇关于(2019杭电多校3) Distribution of books (dp+离散化+线段树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
