题目描述：

　　　　给了两个数组a，b，a[i]和b[i]是相对应的，不能改变位置，去掉其中的一些元素，然后计算最大的r=∑a[i]/∑b[i];

　　这道题乍一看是对a[i]/b[i]进行排序然后取前n-k个，但其实是不对的

题解：由题意得，我们要求的是r，所以对式子进行变形：设A=∑a[i]，B=∑b[i]，则A=r×B，A-r×B=0。所以为了求得最大的r，我们就要求使得A-rxB>0的最大的r，这样我们就可以另ci=ai-bi*r,然后对数组c进行排序即可

代码和学到的东西见下：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define ll long long 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 ll a[1005],b[1005]; 9 double c[1005];10 int n,k;11 bool cmp(ll a,ll b)12 {13     return a>b;14 }15 void trans(double x)16 {17     for(int i=1;i<=n;i++)18     {19         c[i]=100*a[i]-x*b[i];此处可以不乘100,在下面输出的时候再×100,可以省去很多计算20     }21     sort(c+1,c+1+n,cmp);22 }23 void ini()24 {25     mem(a,0);26     mem(b,0);27     mem(c,0);28 }29 int main()30 {31     while(scanf("%d%d",&n,&k)&&k+n>0){32         //ini();33     for(int i=1;i<=n;i++) scanf("%d",a+i);34     for(int i=1;i<=n;i++) scanf("%d",b+i);35     double l=0,r=1000;36     for(int i=1;i<=50;i++)37     {38         double mid=(l+r)/2;39         trans(mid);40         double res=0;41         for(int j=1;j<=n-k;j++)42         {43             res+=c[j];44         }45         if(res>=0) l=mid;46         else if (res<0) r=mid;47         //printf("mid=%lf\n",mid);48     }49     printf("%d\n",(int)((l+r)/2+0.5));}//此处是四舍五入处理50     //此处也可以输出l或者r，因为二分100次后小数位数而让输出整数已经可以忽略l和r的差异51     return 0;52 }
        
       
      
     

二分的题一定要注意精度！！