poj3111-K Best

0 题目

Description

Demy has n jewels. Each of her jewels has some value v_i and weight w_i.

这哥们有n个珠宝，每种珠宝的价值是vi，重量是wi

Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep k best jewels for herself. She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels S = {i₁, i₂, …, i_k} as

因为在紧急危机中他丈夫破产了，这哥们决定卖掉一些珠宝，他决定保存最贵的k个珠宝。他决定为自己保存尽可能价值最大的珠宝。表示为，上面的公式

Demy would like to select such k jewels that their specific value is maximal possible. Help her to do so.

这哥们决定选择k个珠宝，使他们的价值尽可能的最大。

1 分析

按照公式来看，就是在一堆珠宝中，选择k个，使他们的单位重量的价值最大。

1.1 为什么贪心不行

很难讲明白，所以举个例子吧。假设有三种珠宝表示为（价值，重量）：（2,2），（3,5），（1,2）。选取两种。

按照贪心算法，应该选择（2,2），（3,5）或是（2,2），（1,2）。显然这两种选法是贪心的结果，但是其单位重量的价值居然不一样！！！

如果加上一个（6,10）那么贪心就完全是错的了。

所以贪心是不行的。

1.2 难点

这个问题的难点在于，求比值。也就是说，需要选出k个，然后重量相加的W，价值相加得V，然后相除 V/W。枚举？不存在的。

假设已经知道了平均价值为x，那么x=V/W

那么V-W*x=0 ，这个公式中等价于：(v1+v2+v3+...vk)-(w1+w2+w3+...+wk)*x=0

这样，就可以将其中k分子相加，分母分别相加，再求商的过程。改为了每个珠宝单独求，然后将值求和。

但现在的问题是，现在还不知道平均价值x，因此，采用枚举x的方式。

当实际平均价值x，大于我们猜测的平均价值c时。

那么应该被选择的k个珠宝，它们的和 V-W*c 也是大于0的。原因在于V/W=x>c

当实际平均价值，等于我们猜测的平均价值c时

那么应该被选择的k个珠宝中，它们的和 V-W*c 也是等于0的。原因在于V/W=x=c

当实际平均价值，小于于我们猜测的平均价值c时

那么应该被选择的k个珠宝中，它们的和 V-W*c 也是小于0的。原因在于V/W=x<c

然后，每个节点计算出的结果，也就是V-W*c的值，存取来。进行从大到小排序。按照贪心的方法，选前k个，因为前k个的和，一定是最大的。如果前k个的和都小于0，那么其他的就更小于0了。

如果和大于0，表示猜测的c小于x当

bool C(double c)
{
    for(int i=0; i<n; i++)
    {
        y[i] = v[i] - c * w[i];
    }

    sort(y, y+n);

    double sum = 0;
    
    for(int i=0; i<k; i++)
    {
        sum += y[n-i-1];
    }
    return sum >= 0;
}

好在，猜测x的c值并不需要枚举，使用二分法，确定即可。

void solve()
{
    // lb 最小值为0，最大值为 INT_MAX
    double lb = 0, ub = INF;
    for(int i=0; i<100; i++)
    {
        double mid = (lb + ub) / 2;
        if(C(mid)) lb = mid;
        else ub = mid;
    }
    printf("%.2f
",lb);
}

巧妙的1B。

ps：但我的提交并没有通过，一直是Time Limit Exceeded

相当的绝望。刚开始的wrong answer，因为把wv的double，定义成int了。菜的一笔