C语言wyh的物品

题目描述

wyh学长现在手里有 n 个物品，这 n 个物品的重量和价值都告诉你，然后现在让你从中选取 k 个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的 k个物品的总价值和总重量的比值）

输入描述:

输入第一行一个整数 T(1≤T≤10)
接下来有 T组测试数据，对于每组测试数据，第一行输入两个数 n 和 k(1≤k≤n≤100000)
接下来有 n 行，每行两个是 a 和 b (0<a,b≤1000000)代表这个物品的重量和价值

输出描述:

对于每组测试数据，输出对应答案，结果保留两位小数

输入

1
3 2
2 2
5 3
2 1

输出

0.75

说明

对于样例来说，我们选择第一个物品和第三个物品，达到最优目的

 解题思路

题目中说单位价值为选取的 k个物品的总价值和总重量的比值，假设已经选定了k个物品，那么在这k个物品作用下，一个物品的价值x = 这个物品的价值 - 单位价值 * 重量，此时将所有的x累加起来就会有三种情况。

用零来分割，记求和之后的价值为X，如果X>0时，说明了单位价值取小了，需要找大；如果X<0时，说明单位价值取大了，需要找小；如果X=0，说明单位价值刚刚好；

这样来看就可以用二分来解决这个问题了，首先用数组x记入所有的差值，然后再对数组进行排序，这里的排序是降序，因为我们要找最大的单位价值，当X>0时，是需要找大的，所以需要降序；降序之后就可以求和了，求和的话只需要求题目前k项就可以了。

下面是ac代码

int cmp(const void* p1, const void* p2)
{
    return *(double*)p1 > *(double*)p2 ? -1 : 1;
}
int fun(double mid, int n, int k, double* x, int* v, int* w)
{
    double X = 0;
    for (int i = 0; i < n; i++)
    {
        x[i] = v[i] - mid * w[i];
    }
    qsort(x, n, sizeof(double), cmp);//降序排序
    for (int i = 0; i < k; i++)
    {
        X += x[i];//累加的结果
    }
    if (X >= 0)
        return 1;//大于零，mid小了，需要找大，把零归到这里（零去哪里都无所谓），因为是去用左右区间去逼近的，所以零在哪里都可以
    else
        return -1;//小于零，mid大了，需要找小

}

int main()
{

    int t;//需要输入几组测试用例
    scanf("%d", &t);
    while (t--)
    {
        int n, k;
        scanf("%d %d", &n, &k);//n是几个物品，k是选几个物品
        double x[1000000] = { 0 };//单位价值作用下的价值
        int v[1000000] = { 0 }, w[1000000] = { 0 };//v是物品的价值，w是物品的重量
        for (int i = 0; i < n; i++)
            scanf("%d %d", &w[i], &v[i]);
        double left = 0, right = 1000000;
        while (right - left > 0.000001)
        {
            double mid = (left + right) / 2.0;
            if (fun(mid, n, k, x, v, w) == 1)
                left = mid;//mid小了，找大，就让左区间直接跑到中间
            else
                right = mid;//mid大了，找小，让右区间跑到中间
        }
        printf("%.2f\n", left);
    }
    return 0;
}