# PKU POJ 2976 Dropping tests 解题报告

题目链接： <http://acm.pku.edu.cn/JudgeOnline/problem?id=2976>

0-1分数规划

最优比例生成树

迭代法

证明：（前几次都是看别人的，这次自己证明）

对于集合s，令l *= max{ a(x) / b(x) } = a(x*) / b(&#x78;*).l*为所求的最优解，x\*为对应的集合

注：b(x)必须恒大于0

然后令z(l) = min{ l × b(x) - a(x) }

证明单调性：

首先若l1 > l2

z(l1) = min { l1 × b(x) - a(x) } = l1 × b(x1) - a(x1) > l2 × b(x1) - a(x1) ≥ min{ l2 × b(x) - a(x) } = z(l2)

\=>     z(l)是关于l的单调递增函数

再证l = l\*时，z(l) = 0

若有x'使得l\* × b(x') - a(x') ≤ 0

\=>  a(x') / b(x') ≤ l       *=>     l* × b(x') - a(x') ≥ 0

\=>  l *× b(x') - a(x') = 0    即 x' = x*

再证z(l) = 0时l = l\*

若z(l') = 0, l' ≤ max{a(x) / b(x)} = a(&#x78;*) / b(x*)     =>      b(&#x78;*) × l' - a(x*) ≤ 0

\=>  l' = l\*

最终结果是

z(l) < 0 when l < l\*

z(l) = 0 when l = l\*

z(l) > 0 when l > l\*

从这里我们已经可以用二分l的值的方法计算答案了

但是我们要更快，证明迭代法正确性

z(l) = min{l × b(x) - a(x)}

若l1 ≠ l\*

z(l1) = min { l1 × b(x) - a(x) } = l1 × b(x1) - a(x1) 

令l2 = a(x1) / b(x1)      => b(x1) × l2 - a(x1) = 0

若z(l1) < 0 ,则   l2 > l1,同时l\* > l1

又min{ l *× b(x) - a(x) } = 0 < l* × b(x1) - a(x1)   =>  l\* > l2

由此可得   l1 < l2 < l\*

z(l1) < 0时同理可得

最终结论

l1 < l2 < l\*

由此，每次我们计算出l2，必然比l1接近l\*，当靠近到可以忽略精度的位置时，就可以停止了

开始敲代码：

```cpp
/**
* URL: http://acm.pku.edu.cn/JudgeOnline/problem?id=2976
* Author: OWenT
* Blog: http://www.owent.net
* 0-1分数规划 + 最优比例生成树 + 迭代法
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

typedef struct
{
    long a,b;
}node;

node score[1005];
double res = 0, tmp = 100;

double iter(const long &k, const long &n);
bool cmp(node a, node b)
{
    return res * a.b - a.a < res * b.b - b.a;
}

int main()
{
    long n, k, i;
    while(cin>> n>> k, n != 0 || k != 0)
    {
        memset(score, 0, sizeof(score));
        for(i = 0; i < n; i ++)
            cin>> score[i].a;
        for(i = 0; i < n; i ++)
            cin>> score[i].b;
        k = n - k;//去除k个就是取n-k个使得l* = max { a(x) / b(x) }
        res = 0;
        tmp = 100;
        while(fabs(res - tmp) > 1e-6)
        {
            tmp = res;
            res = iter(k, n);
        }

        printf("%.0lf\n", res * 100);
    }
    return 0;
}

double iter(const long &k, const long &n)
{
    long i;
    double tmpRA = 0, tmpRB = 0;
    sort(score, score + n, cmp);
    for(i = 0; i < k; i ++)
        tmpRA += score[i].a, tmpRB += score[i].b;
    return tmpRA / tmpRB;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.owent.net/2010/43.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.