Dropping tests

 

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6373		Accepted: 2198

【Description】

In a certain course, you take n tests. If you get a_i out of b_i questions correct on test i, your cumulative average is defined to be

.

Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

【Input】

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating a_i  for all i. The third line contains n positive integers indicating b_i for all i. It is guaranteed that 0 ≤ a_i ≤ b_i ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

【Output】

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

【Sample Input】

3 15 0 25 1 64 21 2 7 95 6 7 90 0

【Sample Output】

83100

【Hint】

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

【算法分析】

所谓的01分数规划问题就是指这样的一类问题，给定两个数组，a[i]表示选取i的收益，b[i]表示选取i的代价。如果选取i，定义x[i]=1，否则x[i]=0。

每一个物品只有选或者不选两种方案，求一个选择方案即从其中选取k组a[i]/b[i]，使得R=sigma(a[i]*x[i])/sigma(b[i]*x[i])取得最值，即所有选择物品的总收益/总代价的值最大或是最小。

01分数规划问题主要包含一般的01分数规划、最优比率生成树问题、最优比率环问题等。

 

来看目标式：

R=sigma(a[i]*x[i])/sigma(b[i]*x[i])

我们的目标是使得R达到最大或者最小，首先定义一个函数

F(L)=sigma(a[i]*x[i])-L*sigma(b[i]*x[i])，显然这只是对目标式的一个简单的变形。

分离参数，得到F(L):=sigma((a[i]-L*b[i])*x[i])，记d[i]=a[i]-L*b[i]，那么F(L):=sigma(d[i]*x[i])。

 

接下来重点注意一下d[i]和F(L)的单调性。

如果我们已知了L，则所有的的d[i]是已知的，那么这里的贪心策略是为了得到一个最优的F(L)，我们只需要将d[i]排序之后取其中的前k个或者后k个。也就是说，给定L，我们可以直接求出对应的F(L)。

接下来是F(L)，因为b[i]是正的，显然F(L)对于L是单调递减的，这就启发我们可以通过某种方法把F(L)逼近至0，当F(L)=0时，即 sigma(a[i]*x[i])-L*sigma(b[i]*x[i])=0，那么此时的L就是最优值。

 

然后还要注意到的问题是，我们每次贪心地取d[i]中最小的k个，则最终使得F(L)趋于0的L会是最小的比值；如果每次贪心地取d[i]中最大的k个，则最终使得F(L)趋于0的L会是最大的比值。

考虑F(L):=sigma((a[i]-L*b[i])*x[i])式中，我们取了最后k个di[i]使得F(L)=0，则如果用此时的L去取全部的数，F(L)_tot将是小于零的，也即使得整个F(L)_tot趋于0的L_tot是小于L的。故L是取K组数的情况下，最大的比值。（这段说的有点绕口）

 

另外再注意到的一点是，如果将a[i]与b[i]上下颠倒，求解的方法相同，结果跟颠倒前也是刚好相对应的。

 

最后又想到了一个关键点，k的值对最后的结果会是什么影响：

贪心地说，为了使结果尽可能的大，k也要尽可能的大，即尽可能多的舍弃一些，剩下选取的数越少，均值越大

 

总结F(L)的两个重要性质如下就是：

　1.  F(L)单调递减

　2.  F(max(L)/min(L)) = 0

 

之后的逼近方法可以有两种选择

1.二分法

二分区间，不断把F(L)逼近至0，若F(L)<0说明L过大，若F(L)>0说明L过小，直到逼近得到一个最优的L；

1 /* *********************************************** 2 MYID    : Chen Fan 3 LANG    : G++ 4 PROG    : PKU_2976_Erfen 5 ************************************************ */ 6  7 #include 
       
         8 #include 
        
          9 #include 
         
          10 #include 
          
           11 12 #define eps 1e-613 14 using namespace std;15 16 typedef struct nod17 {18     int a,b;19     double r;20 } node;21 22 bool op(node a,node b)23 {24     return a.r>b.r;25 }26 27 node p[1010];28 29 int main()30 {31     freopen("2976.txt","r",stdin);32 33     int n,k;34 35     while(scanf("%d%d",&n,&k))36     {37         if (n==0&&k==0) break;38 39         for (int i=1;i<=n;i++) scanf("%d",&p[i].a);40         for (int i=1;i<=n;i++) scanf("%d",&p[i].b);41 42         int m=n-k;43         double left=0,right=100;44         while (left+eps
           
            0) left=mid;52             else right=mid;53         }54 55         printf("%.0f\n",left*100);56     }57 58     return 0;59 }
           
          
         
        
       

 

2.Dinkelbach

从另外一个角度考虑，每次给定一个L，除了我们用来判定的F(L)之外，我们可以通过重新计算得到一个L'，而且能够证明L'一定是更接近最优解的，那么我们可以考虑直接把L移动到L'上去。当L=L'时，说明已经没有更接近最优的解了，则此时的L就是最优解。

注意在Dinkelbach算法中，F(L)仍然是判定是否更接近最优解的工具，也即此时d[i]的选择仍然与之前相同，只是最后移动解的时候是把L直接移往L' 

1 /* *********************************************** 2 MYID    : Chen Fan 3 LANG    : G++ 4 PROG    : PKU_2976_Dinkelbach 5 ************************************************ */ 6  7 #include 
       
         8 #include 
        
          9 #include 
         
          10 #include 
          
           11 #include 
           
            12 13 #define eps 1e-614 15 using namespace std;16 17 typedef struct nod18 {19     int a,b,index;20     double r;21 } node;22 23 bool op(node a,node b)24 {25     return a.r>b.r;26 }27 28 node p[1010];29 30 int main()31 {32     freopen("2976.txt","r",stdin);33 34     int n,k;35 36     while(scanf("%d%d",&n,&k))37     {38         if (n==0&&k==0) break;39 40         for (int i=1;i<=n;i++) scanf("%d",&p[i].a);41         for (int i=1;i<=n;i++) scanf("%d",&p[i].b);42 43         int m=n-k;44         double l=0,temp=1;45         while (fabs(l-temp)>=eps)46         {47             l=temp;48             for (int i=1;i<=n;i++) p[i].r=p[i].a-l*p[i].b;49             sort(&p[1],&p[n+1],op);50             int x=0,y=0;51             for (int i=1;i<=m;i++) 52             {53                 x+=p[i].a;54                 y+=p[i].b;55             }56             temp=(double)x/y;57         }58 59         printf("%.0f\n",temp*100);60     }61 62     return 0;63 }