Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

上马

Posted by hliyuxin at 2012-06-19 23:23:51 on Problem 1505
#include<iostream>
using namespace std;
#define N 502 
static int v[N],n=0,k=0;
static int l=0,r=0;
static int find(){
	int m=0,i=0,t=0,s=0;
	while(l<r){
		m=l+r>>1; 
		for(i=1,t=s=0;i<=n;++i){
			s+=v[i];
			if(s>m){ s=v[i]; if(++t>=k)break; }
		}
		if(t<k)r=m;
		else l=m+1;
	}
	return l ;
}
static void print(int i,int j,int s,int sum){
	if(i==0)return ;

	if(i<j){ print(i,j-1,0,sum); printf("/ "); return ; }

	s+=v[i]; 
	if( s>sum) { s=v[i]; print(i-1,j-1,s,sum); printf("%d ",v[i]); printf("/ "); }
	else { print(i-1,j,s,sum); printf("%d ",v[i]); }

}
int main(){
	int t=0,i=0;
	freopen("1505_in.txt","r",stdin);
	freopen("1505_out.txt","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		for(i=1,l=r=0;i<=n;++i){ scanf("%d",&v[i]); l=max(l,v[i]); r+=v[i]; }
		i=find();
		print(n,k,0,i); printf("\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator