UVa714 Copying Books(二分答案+贪心)
程序员文章站
2022-03-04 21:08:28
...
题目链接
1.题目大意:把一个正整数序列划分成k个非空的连续子序列,使得每个正整数恰好属于一个序列。设第i个序列的各数之和为S(i),现在我们要让所有S(i)的最大值尽量小。而且如果有多个解,S(1)尽量小,在此前提下S(2)尽量小…,按要求输出
2.最大值尽量小显然是需要二分答案。对于当前得到的答案,我们只需贪心的一直向后选择最大的子区间,即这一段相加小于等于当前答案。如果整个序列划分的个数小于等于k-1,那么当前答案符合要求,继续划分更小的区间,直到得到最后的答案
3.题目要求前面的尽量小,那么,我们就保证后面的尽量大,每次将后面选择到不能大于当前答案为止。但是这样又会导致可能被划分的区间小于k,根据题意就是按前面如果一个数字后面没有区间,就直接插入’/’
4.因为后面我们要从后选择插入’/’,那么我们一开始检查的时候也必须从后面开始检查,这样并不影响最后的划分,因为从前向后划分和从后向前划分都是正确的
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
ll a[505];
int n,k;
bool v[505];
bool check(ll val){
int cnt=1;
ll sum=0;
for(int i=n;i>=1;i--){
if(sum+a[i]<=val)
sum+=a[i];
else{
cnt++;
sum=a[i];
}
if(cnt>k) return 0;
}
return 1;
}
void solve(int val){
ll sum=0;
int cnt=0;
memset(v,0,sizeof v);
for(int i=n;i>=1;i--){
if(sum+a[i]<=val){
sum+=a[i];
}else{
v[i]=1; //当前数不能再加入此序列,因此代表后面有一个'/'
cnt++;
sum=a[i];
}
}
int x=k-cnt-1,p=1; //记录还有几个'/'没有插入
//cout<<x<<endl;
while(x>0 && p<=n){ //贪心从前插入
if(!v[p]){
v[p]=1;
x--;
}
p++;
}
int flag=1;
for(int i=1;i<=n;i++){ //输出
if(flag){
if(!v[i]){
cout<<a[i];
}else cout<<a[i]<<" /";
flag=0;
}else{
if(!v[i]){
cout<<" "<<a[i];
}else cout<<" "<<a[i]<<" /";
}
}
cout<<endl;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
cin>>n>>k;
ll l=-1,r=0; //左边界是所有数的最大值,右边界是所有数的和
for(int i=1;i<=n;i++){
cin>>a[i];
l=max(l,1LL*a[i]);
r+=a[i];
}
ll mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid)){
r=mid;
}else l=mid+1;
}
//cout<<l<<endl;
solve(l);
}
return 0;
}
上一篇: 数据结构与算法之栈的最小值
下一篇: php怎么去掉字符串第一个字符串