首页 > 代码库 > POJ1505Copying Books
POJ1505Copying Books
要吐血了,把k写成m,debug一个多小时,简直无情。。。
#include <iostream> #include<stdio.h> #include<string> #include<cstring> #include<cmath> #include<algorithm> #define N 22222 using namespace std; int a[N]; int sum[N]; int T; int m,k; int vis[N]; int sech(int mid) { int temp=0; int num=1; for(int i=1;i<=m;i++) if(temp+a[i]<=mid) temp+=a[i]; else { num++; temp=a[i]; } if(num<=k) return 1; return 0; } int main() { while(~scanf("%d",&T)) { while(T--) { int le=0,ri; sum[0]=0; scanf("%d%d",&m,&k); for(int i=1;i<=m;i++) { scanf("%d",&a[i]); if(a[i]>le) le=a[i]; sum[i]=sum[i-1]+a[i]; } ri=sum[m]; int mid; int ans; while(le<=ri) { mid=(ri+le)/2; if(sech(mid)) { ans=mid; ri=mid-1; } else le=mid+1; } memset(vis,0,sizeof vis); int temp=0; int x=k; int j; for(j=m;j>=1;j--) { if(x>j)//当人数大于书的本书时,一人翻译一本直到书被翻译完 { for(;j>=1;j--) vis[j]=1; break; } if(temp+a[j]<=ans) temp+=a[j]; else { vis[j]=1; temp=a[j]; x--; } } for(int i=1;i<=m;i++) { if(i==1) printf("%d",a[i]); else printf(" %d",a[i]); if(vis[i]) printf(" /"); } printf("\n"); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。