P4795 可可岛的宝藏（基础）

解题思路

1. 读懂题目：童童的口袋最多装 w 重量的东西。岛上有 s 种金属，每种金属有自己的总重量 nᵢ 和总价值 vᵢ。特别的是，金属可以任意分割，价值与重量成正比（也就是说切下一半，价值也是一半）。问一次最多能带走多少价值。

2. 打个比方：就像去市场买水果，口袋大小有限，不同的水果"每斤价钱"不一样。要想用有限的空间买到最多价值，当然要先买"每斤最贵"的水果，装到满为止。

3. 贪心结论：按"单位重量价值"（价值 ÷ 重量）从高到低排序，优先装单位价值最高的金属。

4. 为什么正确：因为金属可以任意分割，任何一套装法都可以看成"按单价从高到低装"。如果你先装了一部分单价低的金属占掉空间，换成同等重量的单价高的金属，总价值只会更大。所以从单价最高的开始装一定是最优的。

5. 怎么排序避免小数误差：比较两种金属谁单价更高，不需要真的算小数。用交叉相乘：如果 a.value×b.weight > b.value×a.weight，说明 a 的单价更高（两边同时除以 a.weight×b.weight 就变成单价比较）。用 long long 乘，不会丢精度。

6. 装满的过程：按排好的顺序，如果整袋金属重量不超过剩余空间，就整袋装下，价值全部累加，剩余空间减去它的重量；如果整袋装不下，就只装"剩余空间"那么重，这部分价值按比例算：vᵢ × 剩余空间 ÷ nᵢ，然后口袋就满了，停止。

7. 看例子：样例第一组 w=50。按单价排序后是 (10,100)、(7,34)、(87,100)、(50,30)。先装 10 重、价值 100，剩 40；再装 7 重、价值 34，剩 33；再装 33 重（87 的其中 33 份），价值 100×33÷87≈37.93；口袋满。总共约 100+34+37.93=171.93。

8. 边界情况：如果所有金属都装完口袋还没满，那就全部带走；每组测试独立计算，输出保留两位小数。

参考代码

// P4795 可可岛的宝藏：金属可分割，按单位重量价值从高到低装进口袋
#include <iostream>
using namespace std;
struct Metal { int weight; int value; };  // 每种金属的总重量和总价值
Metal metals[105];

// 按单位重量价值（value/weight）从高到低排序
// 用交叉相乘比较，避免浮点数精度误差
void sortMetals(int s) {
    for (int i = 0; i < s - 1; i++)
        for (int j = 0; j < s - 1 - i; j++)
            if ((long long)metals[j].value * metals[j + 1].weight <
                (long long)metals[j + 1].value * metals[j].weight) {
                Metal temp = metals[j];
                metals[j] = metals[j + 1];
                metals[j + 1] = temp;
            }
}

int main() {
    int k;  // 测试数据的组数
    cin >> k;
    while (k--) {
        int w, s;
        cin >> w >> s;
        for (int i = 0; i < s; i++) cin >> metals[i].weight >> metals[i].value;
        sortMetals(s);
        double totalValue = 0;  // 能带走的最大总价值
        int leftWeight = w;     // 口袋剩余还能装的重量
        for (int i = 0; i < s && leftWeight > 0; i++) {
            if (metals[i].weight <= leftWeight) {
                // 整袋全部装下
                totalValue += metals[i].value;
                leftWeight -= metals[i].weight;
            } else {
                // 装不下整袋，按比例切一部分带走
                totalValue += (double)metals[i].value * leftWeight / metals[i].weight;
                leftWeight = 0;
            }
        }
        printf("%.2f\n", totalValue);
    }
    return 0;
}

复杂度分析

每种金属都要和其他金属比较单价来排序，用冒泡排序是 O(s²)，s≤100，很快；装满扫描一遍金属是 O(s)。数据有 k 组，每组独立处理。空间上只用了一个长度为 105 的结构体数组。整体算法轻快，完全符合题目规模。