题目描述

某天 KID 利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID 虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。

但是他只带着一个口袋，口袋至多只能装重量为 w
的物品。

岛上金属有 s
个种类，每种金属重量不同，分别为 n1,n2,…,ns
，同时每个种类的金属总的价值也不同，分别为 v1,v2,…,vs
。

KID 想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。

注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。

输入格式
第 1
行是测试数据的组数 k
，后面跟着 k
组输入。

每组测试数据占 3
行，第 1
行是一个正整数 w
，表示口袋承重上限。

第 2
行是一个正整数 s
，表示金属种类。

第 3
行有 2s
个正整数，分别为 n1,v1,n2,v2,…,ns,vs
分别为第一种，第二种，…，第 s
种金属的总重量和总价值。

输出格式
k
行，每行输出对应一个输入。

输出应精确到小数点后 2
位。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int x, k;
double y;

struct mtl
{
    double n, v, p;
}a[101];

bool cmp(mtl a, mtl b)
{
    return a.p > b.p;
}

int main()
{
    cin >> k;
    while(k--)
    {
        cin >> y >> x;
        for(int i = 1;i <= x;i++)
        {
            cin >> a[i].n >> a[i].v;
            a[i].p = a[i].v / a[i].n;
        }
        sort(a + 1, a + x + 1, cmp);
        int t = y;
        double ans = 0;
        for(int i = 1;i <= x;i++)
        {
            if(t > a[i].n)
            {
                ans += a[i].v;
                t -= a[i].n;
            }
            else
            {
                ans += a[i].p * t;
                t = 0;
            }
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}