官方题解

【算法分析】

最优策略：每一次贪心地选当前单位重量价值最大的金属装入口袋。

【参考代码】

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
	int n; //重量 
	int v; //价值
	double up; //单位重量价值 
};

bool cmp(node x, node y) {
	return x.up > y.up;
}

int main() {
	int k;
	cin >> k;
	while (k--) {
		int w, s;
		double va = 0; //带走的总价值 
		node a[105];
		cin >> w >> s;
		for (int i = 1; i <= s; i++) {
			cin >> a[i].n >> a[i].v;
			a[i].up = a[i].v * 1.0 / a[i].n;
		}
		sort(a + 1, a + s + 1, cmp);
		for (int i = 1; i <= s; i++) {
			if (w - a[i].n < 0) {
				va += a[i].up * w;
				break;
			}
			w -= a[i].n;
			va += a[i].v;
		}
		printf("%.2f\n", va);
	}
	return 0;
}

【时间复杂度】

$O(ks\log_{2}s)$

【预计得分】

$100pts$