7-78 切割绳子 (5分)

有N条绳子，它们的长度分别为Li。如果从它们中切割出K条长度相同的绳子，这K条绳子每条最长能有多长？

输入格式:

第一行两个整数n和k（1<n<10000; 1<k<10000）。 接下来n行，描述了每条绳子的长度Li，Li也是整数。

输出格式:

切割后每条绳子的最大长度。

输入样例:

4 11
802
743
457
539

输出样例:

200


代码讲解:这题我用了俩种办法，一种是顺序的模拟，一种用了二分法，后者复杂度上要好上太多了。


第一种:

#include<stdio.h>
int max_f(int a[],int n)
{
 int i;
 int temp=a[0];
 for(i=1;i<n;i++)
 {
  if(a[i]>temp)
  temp=a[i];
  
 }
 return temp;
 
}
int main()     //复杂度相当高 
{
 int n;
 int li;
 int max;
 scanf("%d %d",&n,&li);
 int a[n];
 int temp;
 int i;
 for(i=0;i<n;i++)
 {
  scanf("%d",a+i);
 }
 max=max_f(a,n);
 int j;
 for(i=max;i>0;i--)
 {
  temp=0;
  for(j=0;j<n;j++)
  {
   temp+=a[j]/i;
  }
  if(temp==li)
  break;
  
 }
 printf("%d\n",i);
 return 0;
}



第二种二分法

#include<stdio.h>
int max_f(int a[],int n)
{
 int i;
 int temp=a[0];
 for(i=1;i<n;i++)
 {
  if(a[i]>temp)
  temp=a[i];
  
 }
 return temp;
 
}
    
int fm(int a[],int n,int x,int m)
{
 int i;
 int li=0;
 for(i=0;i<n;i++)
 {
  li+=a[i]/x;
  
  
 }
 return li>=m;
 
}
int search(int a[],int n,int low,int high,int li)
{
 int  mid;
 while(low<=high)
 { 
 mid=(low+high)/2;
 if(fm(a,n,mid,li))
 {
  low=mid+1;
  
 }
 else
 {
  high=mid-1;
 }
  }
     return high;
 
 
 } 
int main()
{
 int n;
 int li;
 int max;
 scanf("%d %d",&n,&li);
 int a[n];
 int temp;
 int i;
 for(i=0;i<n;i++)
 {
  scanf("%d",a+i);
 }
 max=max_f(a,n);
 int result=search(a,n,0,max,li);
 printf("%d\n",result);
 
 return 0;
 }