金银岛(信息学奥赛一本通 - T1225)

题目描述
某天 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 位。

输入样例
2
50
4
10 100 50 30 7 34 87 100
10000
5
1 43 43 323 35 45 43 54 87 43

输出样例
171.93
508.00

数据范围
1 ≤ s ≤ 100
1 ≤ w ≤ 10000
1 ≤ ni ≤ 10000, 1 ≤ vi ≤ 10000


题解
贪心:

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

const int N = 110;

int T;
int n, m;

struct thing
{
	int v, w;
	double x;
}s[N];

bool cmp(thing a, thing b)
{
	return a.x > b.x;
}

int main()
{
	cin >> T;
	
	while(T --)
	{
		cin >> m >> n;
		for (int i = 1; i <= n; i ++)
		{
		 	cin >> s[i].v >> s[i].w;
		 	s[i].x = 1.0 * s[i].w / s[i].v;
		}
		
		sort(s + 1, s + 1 + n, cmp);
		
		double ans = 0;
		for (int i = 1; i <= n; i ++)
			if(m >= s[i].v)
			{
				m -= s[i].v;
				ans += s[i].w;
			}
			else
			{
				ans += s[i].x * m;
				break;
			}
		
		printf("%.2f\n", ans);
	}
	
	return 0;
}
上一篇:java中生成1000~10000之间的随机数


下一篇:调和级数