Hdu6606 Distribution of books

题意

把一段连续的数字分成k段，不能有空段且段和段之间不能有间隔，但是可以舍去一部分后缀数字，求\(min（max((\sum ai ))\)其中\(\sum ai\)为一段的数字和

分析

最小化最大值问题通常我们要想到二分，所以答案的求法我们就解决了，但是二分我们怎么check呢？这个时候一点思路都没有，我们考虑暴力的算法，设dp[i]表示从1--i最多可以分成多少段，怎么转移，什么情况下可以转移呢?

显然\(dp[i]=max(dp[j]+[sum[i]-sum[j]<=x])\)这样就能取到最多段了，但是这个转移的写法是\(O(n^2)\)的暴力算法，显然不满足题目的复杂度，这就到了这个题目的难点了，如何对dp进行优化，对dp进行优化的方式有多种，单调栈、平行四边形、线段树、主席树等。

关于dp优化：https://blog.csdn.net/qq_35649707/article/details/77834685

这里因为取值满足不等式，而不等式所表示的值域就是天然的区间，区间问题肯定非线段树莫属。我们采用线段树优化，使用权值线段树的节点对应离散化后的sum值,从而维护dp的值，由不等\(sum[i]-sum[j]<=x\)我们转化为\(sum[i]-x<=sum[j]\)即只要找第一个满足该不等式的sum,然后在\([j,m]\)中找最大的dp值即可转移，复杂度就优化到了\(O(nlognlogn)=O(nlog^2n)\)

#include<bits/stdc++.h>

#define pb push_back

#define F first

#define S second

#define pii pair<int,int>

#define mkp make_pair

typedef long long ll;

using namespace std;

const int maxn=2e5+5;

int tr[maxn<<2];

int a[maxn];

ll sum[maxn],v[maxn];

int t,n,k,flag,cnt=0,sz;

void build(int o,int l,int r){

	tr[o]=-maxn;

	if(l==r)return ;

	int mid=l+r>>1;

	build(o<<1,l,mid);

	build(o<<1|1,mid+1,r);

}

void update(int o,int l,int r,int p,int v){

	if(l==r)tr[o]=max(tr[o],v);

	else {

		int mid=l+r>>1;

		if(mid>=p)update(o<<1,l,mid,p,v);

		else update(o<<1|1,mid+1,r,p,v);

		tr[o]=max(tr[o<<1],tr[o<<1|1]);

	}

}

int query(int o,int l,int r ,int x,int y){

	if(x<=l&&y>=r)return tr[o];

	int mid=l+r>>1;

	int ans=-maxn;

	if(mid>=x)ans=max(ans,query(o<<1,l,mid,x,y));

	if(mid<y)ans=max(ans,query(o<<1|1,mid+1,r,x,y));

	return ans;

}

bool  check(ll x){

	build(1,1,sz);

	for(int i=1;i<=n;i++){

		int l=lower_bound(v+1,v+1+sz,sum[i]-x)-v;

		int id=lower_bound(v+1,v+1+sz,sum[i])-v;

		//cout<<" i "<<i<<" l "<<l<<" id "<<id<<" sum-x "<<sum[i]-x<<endl;

		if(l>sz){

			if(sum[i]<=x)

			update(1,1,sz,id,1);

		}

		else {

			int t=query(1,1,sz,l,sz);

			//cout<<i<<" t "<<t<<endl;

			if(t==-maxn){

				if(sum[i]<=x)

				update(1,1,sz,id,1);

			}

			else

			update(1,1,sz,id,t+1);

		}

	}

	//cout<<query(1,1,sz,1,sz)<<endl;

	return query(1,1,sz,1,sz)>=k;

}

int main(){

	scanf("%d",&t);

	while(t--){

		cnt=1;

		scanf("%d%d",&n,&k);

		for(int i=1;i<=n;i++){

			scanf("%d",&a[i]);

			sum[i]=sum[i-1]+a[i];

			v[cnt++]=(sum[i]);

		}

		cnt--;

		sort(v+1,1+v+cnt);

		sz=unique(v+1,v+1+cnt)-v-1;

	//	for(int i=1;i<=sz;i++)cout<<v[i]<<" ";

	//	cout<<endl;

		//cout<<sz<<endl;

		ll l=-1e14;

		ll r=-l;

		ll ans=1e15;

		while(l<=r){

			ll mid=l+r>>1;

			//cout<<l<<" "<<r<<endl;

			if(check(mid)){

				ans=min(ans,mid);

				r=mid-1;

			}

			else l=mid+1;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

HDU多校第三场 Hdu6606 Distribution of books 线段树优化DP

Hdu6606 Distribution of books

题意

分析

最新文章

热门文章