50674

UVA714 抄书 Copying Books

<h3 id="洛咕">洛咕</h3> <h3 id="题意把一个包含n个正整数的序列划分成m段1nm500非空的连续子序列使得每个正整数恰好属于一个序列.设第i个序列的各数之和为si你的任务是让max_si最小输出划分的方案.">题意:把一个包含\(n\)个正整数的序列划分成\(m\)段\((1<=n<=m<=500)\)非空的连续子序列,使得每个正整数恰好属于一个序列.设第i个序列的各数之和为\(S(i)\),你的任务是让\(max_{S(i)}\)最小,输出划分的方案.</h3> <h3 id="分析使得每一段和的最大值尽量小是一个裸的二分答案.但是这个输出方案很麻烦.不过我们还是先求出这个max_si然后根据这个来求方案.">分析:使得每一段和的最大值尽量小是一个裸的二分答案.但是这个输出方案很麻烦.不过我们还是先求出这个\(max_{S[i]}\),然后根据这个来求方案.</h3> #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #include<map> #include<set> #define ll long long using namespace std; inline int read(){ int x=0,o=1;char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')o=-1,ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*o; } const int N=505; int n,m,a[N],bj[N]; inline bool check(int mid){//二分答案 int now=a[1],cnt=1; for(int i=2;i<=n;++i){ if(now+a[i]<=mid)now+=a[i]; else ++cnt,now=a[i]; } return cnt<=m; } int main(){ int T=read(); while(T--){ n=read();m=read(); ll l=0,r=0;int mid,ans;//r会爆int for(int i=1;i<=n;++i){ a[i]=read(); l=max(l,1ll*a[i]);r+=a[i];//二分答案的上界和下界 } while(l<=r){ mid=(l+r)>>1; if(check(mid)){ ans=mid; r=mid-1; } else l=mid+1; }//求得每一段和的最大值的最小值为ans for(int i=1;i<=n;++i)bj[i]=0;//bj[i]=1,在i后面要划一刀 int now=0,res=m;//now当前这一段的和,我们还要划分出res段 for(int i=n;i>=1;--i){//题目要求靠前面的段的和尽量小,所以倒序划分 if(res>i)bj[i]=1,--res;//这种情况的话,接下来每个数都自成一段 else if(now+a[i]>ans)bj[i]=1,--res,now=a[i];//这一段不能再塞进a[i]了 else now+=a[i];//能塞就塞,保证前面的子段和会尽量小 } printf("%d",a[1]);//接下来就按照题意输出 if(bj[1])printf(" /"); for(int i=2;i<=n;++i){ printf(" %d",a[i]); if(bj[i])printf(" /"); } puts(""); } return 0; }

来源:博客园

作者:PPXppx

链接:https://www.cnblogs.com/PPXppx/p/11426199.html

Recommend