android教程 Transformer xamarin iis axios mockito Keys.js vue传值 vue的优点 jq延时 webapp打包 matlab求向量的模 python学习 python3文件操作 python教程 python语言编程 python循环10次 java字符串长度 java查找字符串 java的数据结构 java什么是多态 java语言简介 java语言编程 java网页 php入门例子 mounted 摩斯电码翻译器 eml文件阅读器下载 迅雷去广告版 狮子狗皮肤 js刷新页面 gg修改器下载 苹果手机总是自动重启 我的世界透视 jarsigner 奥法隐藏外观 经典雅黑 python列表求和 透视网格工具怎么取消 backtrack4
当前位置: 首页 > 学习教程  > 编程语言

HDU-1009.FatMouse‘Trade

2020/7/24 10:51:49 文章标签:

在这里插入图片描述
题意

这是需要用M磅猫粮去和猫兑换仓库中的JavaBean,每个仓库中的JavaBean数量和价格不完全一致,如何才能兑换到更多的JavaBean
这里有一句大致意思是:不要买完仓库中的全部

思路

这是一个简答贪心问题,我只需要每次购买当前剩余产品中性价比最高的产品即可
如果能全换完,那就换完,否则兑换等比例JavaBean

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1000;
struct JavaBean{
	double weight;
	double cost;
}; 

JavaBean a[MAXN]; 

bool cmp(JavaBean x,JavaBean y)
{
	return x.weight/x.cost>y.weight/y.cost;
}

int main(void)
{
	int n,m;
	while(scanf("%d %d",&n,&m) != EOF)
	{
		if(n==-1 && m==-1)break;
		for(int i=0;i<m;++i)
		{
			scanf("%lf %lf",&a[i].weight,&a[i].cost);
		}
		sort(a,a+m,cmp); //将权值大的放在前面,最先兑换,权值小的放在后边 
		double answer=0;
		for(int i=0;i<m;++i)
		{
			if(n>=a[i].cost)
			{
				n-=a[i].cost;
				answer+=a[i].weight;
			}
			else//如果不能全部兑换,则兑换部分,因为这个题可以不全部买完 
			{
				answer +=a[i].weight *(n/a[i].cost);
				n=0;
				break;
			}
		}
		printf("%.3lf\n",answer);
	}
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_50341.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?