ζ

POJ2976-Dropping tests

    题解

题目大意：给出n件物品， 第i件物品有两个属性a[i]和b[i]。令

y=100×a1+a2+a3+...+anb1+b2+b3+...+bny=100 \times \frac{a_1+a_2+a_3+...+a_n}{b_1+b_2+b_3+...+b_n}

问：在这些物品中删除恰好k件物品后，剩下物品的y值最大为多少。

就是二分查找可能取得的最大值。最开始想错了验证答案可行性的方法，错误地认为物品删除的顺序不影响答案的验证。写出了错误代码（ver.1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
double a[1005], b[1005];
int n, k;
bool C(double x)
{
    double suma = 0, sumb = 0;
    x /= 100;
    int i, sum = 0;
    for (i = 1; i <= n; i++)
    {
        if ((suma + a[i]) / (sumb + b[i]) < x)
        {
            sum++;
            if (sum > k)
                return false;
            continue;
        }
        suma += a[i];
        sumb += b[i];
    }
    return true;
}
int main()
{
    int i;
    double l, r, m, res;
    while (scanf("%d%d", &n, &k))
    {
        if ((n | k) == 0)
            return 0;
        for (i = 1; i <= n; i++)
            scanf("%lf", &a[i]);
        for (i = 1; i <= n; i++)
            scanf("%lf", &b[i]);
        l = 0;
        r = 100;
        for (i = 1; i <= 100; i++)
        {
            m = l + (r - l) / 2;
            if (C(m))
            {
                res = m;
                l = m;
            }
            else
                r = m;
        }
        printf("%.0f\n", res);
    }
}

然而，这个代码虽然能过样例但是WA了。如果整体删掉k个是满足答案的，而最开始就将试图所有对答案有负面影响的物品，而不将它们与后面较大的物品综合是不行的。比如这组数据

1
2
3
3 1
0 0 1
1 1 1

最终答案应该是33，但输出的是0。因为前两个0在那里，后面的物品怎么都取不到了。

那么应该怎么删？假设待验证的答案为x，那么要验证的其实就是

100×∑i=1nai∑i=1nbi≥x100 \times \frac{\sum_{i=1}^{n}a_i}{\sum_{i=1}^{n}b_i} \geq x

这个式子是否正确。

简单起见，这里的这个100先不管，到输出答案的时候再乘起来，那么要验证的式子就变成了

∑i=1nai∑i=1nbi≥x\frac{\sum_{i=1}^{n}a_i}{\sum_{i=1}^{n}b_i} \geq x

将分母乘到右边，

∑i=1nai≥x×∑i=1nbi∑i=1nai−x×∑i=1nbi≥0∑i=1n(ai−bix)≥0\sum_{i=1}^{n}a_i \geq x \times \sum_{i=1}^{n}b_i \\ \sum_{i=1}^{n}a_i-x \times \sum_{i=1}^{n}b_i \geq 0\\ \sum_{i=1}^{n}(a_i-b_ix) \geq 0

所以只要算出所有的c[i] = a[i] - b[i] * x，从小到大排序，看看将最小的k个删掉之后，剩下的这些c之和是否不小于0，如果不小于0，就说明当前的这个x是可行的了。

于是又能写出错误代码（ver.2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
double a[1005], b[1005], c[1005];
int n, k;
bool C(double x)
{
    int i;
    double sum = 0;
    for (i = 1; i <= n; i++)
    {
        c[i] = a[i] - b[i] * x;
        sum += c[i];
    }
    sort(c + 1, c + 1 + n);
    for (i = 1; i <= k; i++)
    {
        sum -= c[i];
        if (sum >= 0)
            return true;
    }
    return false;
}
int main()
{
    int i;
    double l, r, m, res;
    while (scanf("%d%d", &n, &k))
    {
        if ((n | k) == 0)
            return 0;
        for (i = 1; i <= n; i++)
            scanf("%lf", &a[i]);
        for (i = 1; i <= n; i++)
            scanf("%lf", &b[i]);
        l = 0;
        r = 1;
        for (i = 0; i <= 100; i++)
        {
            m = l + (r - l) / 2;
            if (C(m))
            {
                res = m;
                l = m;
            }
            else
                r = m;
        }
        printf("%.0f\n", res * 100);
    }
}

又是能过样例但是WA，这个错误比较隐性，是因为当某一组测试数据的最终答案只能取0时，res不会更新。这是困扰我最久的一个错误代码，因为原数据中实际上是没有输出整0的数据的，这么写只会导致当需要输出0.00xxx之类很小的数字时会出错，所以我写了一个使用eps判断浮点数大小的代码就水过了，这一度令我感到十分费解。

改正了这个错误，还痛改前非地改变了二分的风格，得到了如下的错误代码（ver.3）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
double a[1005], b[1005], c[1005];
int n, k;
bool C(double x)
{
    int i;
    double sum = 0;
    for (i = 1; i <= n; i++)
    {
        c[i] = a[i] - b[i] * x;
        sum += c[i];
    }
    sort(c + 1, c + 1 + n);
    for (i = 1; i <= k; i++)
    {
        sum -= c[i];
        if (sum >= 0)
            return true;
    }
    return false;
}
int main()
{
    int i;
    double l, r, m;
    while (scanf("%d%d", &n, &k))
    {
        if ((n | k) == 0)
            return 0;
        for (i = 1; i <= n; i++)
            scanf("%lf", &a[i]);
        for (i = 1; i <= n; i++)
            scanf("%lf", &b[i]);
        l = 0;
        r = 1;
        for (i = 0; i <= 100; i++)
        {
            m = l + (r - l) / 2;
            if (C(m))
                l = m;
            else
                r = m;
        }
        printf("%.0f\n", l * 100);
    }
}

又是能过样例但是WA。这回的错误也比较隐性：当k=0时，C函数无论如何都会输出false，因为不会进那个for循环。改了这个之后终于得到了正确的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
double a[1005], b[1005], c[1005];
int n, k;
bool C(double x)
{
    int i;
    double sum = 0;
    for (i = 1; i <= n; i++)
    {
        c[i] = a[i] - b[i] * x;
        sum += c[i];
    }
    sort(c + 1, c + 1 + n);
    for (i = 1; i <= k; i++)
    {
        sum -= c[i];
        if (sum >= 0)
            return true;
    }
    return sum >= 0;
}
int main()
{
    int i;
    double l, r, m;
    while (scanf("%d%d", &n, &k))
    {
        if ((n | k) == 0)
            return 0;
        for (i = 1; i <= n; i++)
            scanf("%lf", &a[i]);
        for (i = 1; i <= n; i++)
            scanf("%lf", &b[i]);
        l = 0;
        r = 1;
        for (i = 0; i <= 100; i++)
        {
            m = l + (r - l) / 2;
            if (C(m))
                l = m;
            else
                r = m;
        }
        printf("%.0f\n", l * 100);
    }
}
页阅读量:  ・  站访问量:  ・  站访客数: