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