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 chenlingkui at 2009-02-07 00:38:54 on Problem 1064
#include<stdio.h>
main()
{float lns[10000]={0},he=0,max,m2max,rmax,k,start,end;//rmax=real max;
int nor,nog,mmax,i,duan[10000]={0},duhe=0;//nor=number of the rope;nog=number of the geshu(减后的个数),mmax=middle max;
scanf("%d%d",&nor,&nog);
	for(i=0;i<nor;i++)
	{scanf("%f",&lns[i]);
	he=lns[i]+he;
	}
max=he/nog*100.0;mmax=max;m2max=mmax;
rmax=m2max/100.0;//差一个小数,在mmax=max的位置
for(k=rmax/2,end=rmax,start=0;;)//折半法
	{	for(i=0;i<nor;i++)
		{duan[i]=lns[i]/k;
		duhe=duhe+duan[i];
		}
	if(duhe==nog)break;
	else if(duhe>nog)start=k;
	else end=k;
	k=(end+start)/2;
	duhe=0;
	}
for(duhe=0;;k=k+0.01)//找最大的
	{for(i=0;i<nor;i++)
		{duan[i]=lns[i]/k;
		duhe=duhe+duan[i];
		}
	if(duhe!=nog)break;
	duhe=0;
	}
k=k-0.01;
printf("%.2f\n",k);
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