当前位置: 代码迷 >> 综合 >> FatMouse's Trade【九度教程第21题】
  详细解决方案

FatMouse's Trade【九度教程第21题】

热度:24   发布时间:2024-01-10 14:25:44.0

题目描述:

FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i] * a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.

输入:

The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1’s. All integers are not greater than 1000.

输出:

For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.

样例输入:

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

样例输出:

13.333
31.500

解释题目

题目大概可以化为用固定的钱买东西,求一种方案使得买到东西奖励最大。
一共有M元钱,有N种商品可供购买,每种商品个数仅有一个,且每种商品都有一个固定的奖励(reward),如何花钱使得买到商品的奖励最大?(无法买的起的话 按照剩余钱给相应的奖励)

贪心策略

贪心算法实际上就是一个追求性价比的过程,这道题目里的性价比就是每种商品的奖励/商品的价格,当这个性价比越大,我们就越应该买它。所以这道题的贪心策略就是选择性价比最高的买

代码

根据之前刷的几道题,代码基本的框架流程应该很清晰了,重要包括

  1. 控制台多组输入?while (scanf("%d", &n) != EOF)
  2. 每行什么结构存储?struct

然后这道题里比较重要的点在:

  1. 先算每个商品的性价比,然后对性价比进行排序 sort函数
  2. 额外的约束退出条件在哪添加?
#define _CRT_SECURE_NO_WARNINGS // 用来解除scanf的安全检查 或者 手动设置项目属性取消SDL检查
#include<stdio.h>
#include<algorithm>using namespace std;
struct goods {
    double f; //商品奖励double j; //商品价格double s; //商品性价比
}buf[1000];
bool cmp(goods a, goods b) {
    //定义规则 按照从大到小的顺序排列return a.s > b.s;
}int main(){
    double m;int n;while (scanf("%lf%d", &m, &n) != EOF) {
     //常规if (m == -1 && n == -1) //额外判断break;for (int i = 0; i < n; i++) {
    scanf("%lf%lf", &buf[i].f, &buf[i].j);buf[i].s = buf[i].f / buf[i].j;}sort(buf, buf + n, cmp);int idx = 0;double ans = 0;while (m > 0 && idx < n) {
    if (m > buf[idx].j) {
    // 剩余钱可以买目标商品ans += buf[idx].f;m -= buf[idx].j;idx++;}else {
     //剩余钱买不起所有目标商品,根据题意 按比例得到奖励ans += buf[idx].f * m / buf[idx].j;m = 0;// 没钱了 结束了}}printf("%.3lf", ans);}return 0;
}