| ||||||||||
| 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 | |||||||||
二分+贪心 都是一类很经典的问题 二分查找最小的最大区间 每次贪心地尝试能不能覆盖全部区间 最后贪心输出#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int book[510],n;
bool cover(int range,int k,int pivot)
{
int cnt=1,page=0;
for(int i=pivot;i<=n;i++)
if(book[i]<=range)
{
if(page+book[i]<=range)
page+=book[i];
else cnt++,page=book[i];
if(cnt>k) return false;
}
else return false;
return true;
}
int main()
{
int t,k;
cin>>t;
while(t--)
{
int l=0,r=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&book[i]),r+=book[i];
while(l<r)
{
int m=(l+r)>>1;
if(cover(m,k,1))
r=m;
else l=m+1;
}
for(int i=1,j=1;i<=k;i++)
if(i<k)
{
int cur=book[j];
printf("%d ",book[j++]);
for(;j<=n && (cur+=book[j])<=l && !cover(l,k-i,j);j++)
printf("%d ",book[j]);
printf("/ ");
}
else
{
for(;j<=n;j++)
printf("%d ",book[j]);
}
puts("");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator