| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
二分+贪心~ac代码#include<iostream>
#include<cstdio>
#include<algorithm>
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define PI acos((double)-1)
#define E exp(double(1))
const int K=1000+9;
int a[K],n,m,d[K];
bool check(int k)
{
for(int i=1,sum=0,seg=0;i<=n;i++)
{
sum+=a[i];
if(sum>k)
seg++,sum=a[i];
if(seg>=m||sum>k)
return 0;
}
return 1;
}
int main(void)
{
int t;cin>>t;
while(t--)
{
int ans,l,r,mid;
l=0,r=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),r+=a[i];
while(l<=r)
{
mid=l+r>>1;
if(check(mid))
r=mid-1,ans=mid;
else
l=mid+1;
}
for(int i=n,sum=0,cnt=--m;i;i--)
{
if(i==cnt)
{
for(int j=1;j<=i;j++)
d[j]=j;
break;
}
sum+=a[i];
if(sum>ans)
d[cnt--]=i,sum=a[i];
}
for(int i=1,j=1;i<=m;i++)
{
while(j<=d[i])
printf("%d ",a[j++]);
printf("/ ");
}
for(int i=d[m]+1;i<=n;i++)
printf("%d%c",a[i],i==n?'\n':' ');
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator