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(x).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(x) / b(x)     =>      b(x) × 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*，当靠近到可以忽略精度的位置时，就可以停止了

开始敲代码：

/**
* 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;
}