poj 2976Dropping tests解题报告

01分数规划，有一个序列ai,和一个序列bi，从中取出下标相等的m个数，使得∑a[i]/∑b[i]最大，刚开始用dp做的，TLE了，看了别人的题解，二分

View Code

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<stdlib.h>
 4 #define N 1005
 5 #define eps 1e-2
 6 double a[N],b[N];
 7 double val[N];
 8 int cmp(const void *a,const void *b)
 9 {
10     double c=*(double *)a;
11     double d=*(double *)b;
12     if(c>d)
13     return -1;
14     return 1;
15 }
16 int main()
17 {
18     int n,k,i,j;
19     double low,high,sum,mid;
20     while(scanf("%d%d",&n,&k)&&(n||k))
21     {
22         low=0,high=100;
23         for(i=0;i<n;i++)
24         scanf("%lf",&a[i]);
25         for(i=0;i<n;i++)
26         scanf("%lf",&b[i]);
27         while(fabs(high-low)>eps)
28         {
29             sum=0;
30             mid=(low+high)/2.0;
31             for(i=0;i<n;i++)
32             val[i]=a[i]*100-mid*b[i];//这里有些不懂啊，唉
33             qsort(val,n,sizeof(double),cmp);
34             for(i=0;i<n-k;i++)
35             sum+=val[i];
36             if(sum>0)
37             low=mid;
38             else
39             high=mid;
40         }
41         printf("%.0lf\n",mid);
42     }
43     return 0;
44 }