首页 > 编程语言 >南沙C++信奥赛陈老师解一本通题 1225:金银岛

南沙C++信奥赛陈老师解一本通题 1225:金银岛

时间:2024-11-06 16:21:22浏览次数:1  
标签:... 1225 10000 int 信奥赛 金属 通题 n2 unit

 【题目描述】

某天KID利用飞行器飞到了一个金银岛上,上面有许多珍贵的金属,KID虽然更喜欢各种宝石的艺术品,可是也不拒绝这样珍贵的金属。但是他只带着一个口袋,口袋至多只能装重量为w的物品。岛上金属有ss个种类, 每种金属重量不同,分别为n1,n2,...,nsn1,n2,...,ns,同时每个种类的金属总的价值也不同,分别为v1,v2,...,vsv1,v2,...,vs。KID想一次带走价值尽可能多的金属,问他最多能带走价值多少的金属。注意到金属是可以被任意分割的,并且金属的价值和其重量成正比。

【输入】

第1行是测试数据的组数kk,后面跟着kk组输入。

每组测试数据占3行,第1行是一个正整数w(1≤w≤10000)w(1≤w≤10000),表示口袋承重上限。第2行是一个正整数s(1≤s≤100)s(1≤s≤100),表示金属种类。第3行有2s2s个正整数,分别为n1,v1,n2,v2,...,ns,vsn1,v1,n2,v2,...,ns,vs分别为第一种,第二种,...,第ss种金属的总重量和总价值(1≤ni≤10000,1≤vi≤10000)(1≤ni≤10000,1≤vi≤10000)。

【输出】

kk行,每行输出对应一个输入。输出应精确到小数点后22位。

【输入样例】

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
#include <bits/stdc++.h>
using namespace std;
struct Node
{
	int w;
	int v;
	double unit;
};
Node a[1001];
bool cmp(Node n1,Node n2)
{
	return n1.unit>n2.unit;
}
int main()
{
	int k,s,n;
	cin>>k;
	while(k--)
	{
		cin>>n>>s;
		double ans=0;
		for(int i=1;i<=s;i++)
		{
			cin>>a[i].w>>a[i].v;
			a[i].unit=a[i].v*1.0/a[i].w;
		}
		sort(a+1,a+1+s,cmp);		//按单价从大到小排序 
		for(int i=1;i<=s;i++)
		{
			if(n>=a[i].w)	//全装下还有剩 
			{
				ans+=a[i].w*a[i].unit;
				n-=a[i].w;
			}
			else //不够装 只装n 
			{
				ans+=n*a[i].unit;
				break;
			}
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}

 

标签:...,1225,10000,int,信奥赛,金属,通题,n2,unit
From: https://www.cnblogs.com/nanshaquxinaosai/p/18530488

相关文章

  • CSP/信奥赛C++完整学习规划(价值2万的csp-j完整课程体系)
    CSP/信奥赛C++课程完整学习视频一站式掌握信奥赛知识冲刺信奥赛拿奖课程购买后永久学习,不受限制!阶段一:《信奥赛C++语法基础》课程目标:轻松入门C++语法课程链接:https://edu.csdn.net/course/detail/39557阶段二:《信奥赛C++语法进阶》课程目标:快速进阶C++语法......
  • 南沙C++信奥赛陈老师解一本通题 1345:【例4-6】香甜的黄油
    ​ 【题目描述】农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1≤N≤500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。农夫John很狡猾。像以前的巴甫洛夫,他知道他可以训练这些奶牛,让它们在听到铃声时......
  • 【信奥赛·算法基础】插入排序:算法解析与C++实现
    序言插入排序(InsertionSort)是一种简单的排序算法,就像是我们在打扑克牌时,整理手中牌的过程。一、基本原理插入排序的基本思想是:将待排序的元素插入到已经有序的部分序列中合适的位置,直到所有元素都插入完毕,整个序列就变为有序序列。二、算法步骤从第二个元素开始(假设第......
  • CSP/信奥赛C++刷题训练:经典二分例题(2):洛谷P1678:烦恼的高考志愿
    CSP/信奥赛C++刷题训练:经典二分例题(2)烦恼的高考志愿题目背景计算机竞赛小组的神牛V神终于结束了高考,然而作为班长的他还不能闲下来,班主任老t给了他一个艰巨的任务:帮同学找出最合理的大学填报方案。可是v神太忙了,身后还有一群小姑娘等着和他约会,于是他想到了同为计......
  • 【信奥赛·算法基础】CSP-J 枚举算法
    序言解决问题,并不是一开始就要找到最优解,而是在不断的调试中优化,将求解过程中耗时的部分、占用空间的部分尽可能的缩小,使得程序运行起来更高效一、定义与概念枚举算法,也叫穷举算法,是一种简单而直接的问题求解策略。它的核心思想是逐一列举问题的所有可能解,并逐一检验每个......
  • 【信奥赛·算法基础】CSP-J C++ 贪心算法示例汇总
    序言为了更清晰的了解贪心算法,我把常见的贪心算法示例做了一个总结,把问题和策略,以及代码示例放到了一起,方便学习和分析,这里示例仅以C++为例,其他语言可根据示例调整即可一、钱币找零问题问题描述:给定不同面额的钱币以及每种面额的数量,用最少的钱币张数凑齐给定的总金额。......
  • 题解:CF1225E Rock Is Push
    很玄妙的一道dp题。HintAnalysis首先你要确保你会做当石头没有/固定的情况,这道题其实也是dp。考虑石头带来的影响,唯一的作用就是限制你的移动,比方说你下面有\(3\)块石头,由于只能向右或向下移动,你实际上往下只能走到当前列第\(n-3\)行。于是对于石头的处理,设\(rs[i][j......
  • 【信奥赛·C++基础语法】CSP-J C++ STL 标准模板库 - 算法
    序言标准模板库(STL)的算法部分提供了一系列强大的工具,用于对各种容器中的数据进行操作。这些算法可以大大提高编程效率,减少代码重复,使程序更加简洁、高效和可读。无论是处理简单的数据结构还是复杂的大规模数据,STL算法都能发挥重要作用。一、STL算法的分类排序算法快速......
  • 南沙C++信奥赛陈老师解一本通题 1286:怪盗基德的滑翔翼
    ​【题目描述】怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪......
  • 【信奥赛·C++基础语法】CSP-J C++ 指针与引用
    序言指针和引用是非常重要的概念,它们提供了对内存的直接访问和操作方式,使得程序员能够更加灵活地处理数据哈,理解指针和引用的工作原理以及正确使用它们,对于编写高效、安全的C++程序至关重要。一、指针的基本概念指针的定义和作用指针是一个变量,它存储了另一个变量的内......