当前位置: 代码迷 >> 综合 >> HDU.1009 FatMouse' Trade
  详细解决方案

HDU.1009 FatMouse' Trade

热度:80   发布时间:2024-01-27 04:48:41.0

文章目录

  • 一、题目解读
    • 1、原题
    • 2、分类
    • 3、题意
    • 4、输入输出格式
    • 5、数据范围
  • 二、题解参考
    • 1、总体思路
    • 2、思路①
      • (1).分析
      • (2).一些数据
      • (3).AC代码
  • 三、评价与后话
    • 1、评价
    • 2、G++的坑
    • 3、后话

一、题目解读

1、原题

HDU.1009 FatMouse’ Trade

2、分类

  • 贪心
  • 背包——多重背包

3、题意

老鼠有 M M 个猫币,猫有鼠币 N N 堆(每堆数量为 J i J_i )、并为每一堆提供了 1 1 种兑换比率 J i : F i J_i:F_i (用 F i F_i 个猫币可以换来 J i J_i 个鼠币),试问老鼠最多能用 M M 个猫币换回多少鼠币?

再进一步简化,既然猫的鼠币是可以部分兑换的,那么我们只要给 N N 种兑换比率对性价比进行排序,然后从性价比高的到低的一直到兑换结束就可以了。那么原问题就等价于在问,排列性价比 J i F i \frac{J_i}{F_i} ,然后据此计算收获。

4、输入输出格式

输入/输出 要求与格式
输入样例个数 通过输入 M = ? 1 M=-1 N = ? 1 N=-1 标识输入结束
输入格式(每个样例) 第一行输入两个数 M M N N ,后 N N 行(空格隔开)每行输入两个数 J i J_i F i F_i (空格分开)
输出格式(每个样例) 每行输出一个结果
输出精度 保留小数点后 3 3

5、数据范围

数据 范围
一切输入 t t 0 t < 1000 0 \leq t < 1000

二、题解参考

1、总体思路

思路 时间复杂度 具体解释
STL——sort O ( n log ? n ) O(n \log n) 排完序尽量按照大的性价比兑换

2、思路①

(1).分析

在输入的时候,将免费兑换的直接统计到结果中,然后将不是免费的数据添加到数据列表中。

对非免费的数据列表根据性价比进行排序,这里就用STL里的sort函数就行了,可以重载小于运算符,也可以自定义函数然后传入sort作为参数。

排完序后开启循环进行兑换,从性价比大的开始兑换(res += ???),直到所有猫能提供的所有物资都被兑换完(cnt_t == cnt)或者老鼠的本金全部消耗完毕(fabs(left) < 1e-6)。

最后打印计算结果。

(2).一些数据

  • 坑爹数据1——免费兑换
    2 1
    1 0输出结果:1.000
    
  • 坑爹数据2——没有本金
    0 1
    1 1输出结果:0.000
    
  • 坑爹数据3——免费兑换+没有本金
    0 3
    1 0
    2 0
    1 1输出结果:3.000
    
  • 其他数据
    5 4
    2 2
    1 1
    0 0
    0 0输出结果:3.000
    

(3).AC代码

HDU(C++)AC代码如下:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>using namespace std;struct node
{int get;int price;bool operator<(const node& n1)const{return double(get) / price > double(n1.get) / n1.price;}
}us[1005];int main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int M, N;int cnt;double res;int g, p;while (cin >> M >> N, M != -1 || N != -1){cnt = 0;res = 0;for (int i = 0; i < N; ++i){cin >> g >> p;if (p == 0){res += g;continue;}us[cnt].get = g;us[cnt].price = p;++cnt;}sort(us, us + cnt);int cnt_t = 0;double left = M;while (fabs(left) > 1e-6 && cnt_t < cnt){double real_get = min(double(us[cnt_t].get), double(left) * us[cnt_t].get / us[cnt_t].price);double real_price = min(double(us[cnt_t].price), left);res += real_get;left -= real_price;++cnt_t;}cout << fixed << setprecision(3) << res << endl;}return 0;
}

HDU(G++)AC代码如下:

#include <cstdio>
#include <algorithm>
#include <cmath>using namespace std;struct node
{int get;int price;bool operator<(const node& n1)const{return double(get) / price > double(n1.get) / n1.price;}
}us[1005];int main()
{int M, N;int cnt;double res;int g, p;while (scanf("%d %d", &M, &N), M != -1 || N != -1){cnt = 0;res = 0;for (int i = 0; i < N; ++i){scanf("%d %d", &g, &p);if (p == 0){res += g;continue;}us[cnt].get = g;us[cnt].price = p;++cnt;}sort(us, us + cnt);int cnt_t = 0;double left = M;while (fabs(left) > 1e-6 && cnt_t < cnt){double real_get = min(double(us[cnt_t].get), double(left) * us[cnt_t].get / us[cnt_t].price);double real_price = min(double(us[cnt_t].price), left);res += real_get;left -= real_price;++cnt_t;}printf("%.3lf\n", res);}return 0;
}

三、评价与后话

1、评价

这道题应该是贪心算法里一道比较简单的题目,但是有些情况往往容易被忽略,因此以后遇到一些题目开始的时候或者AC不了的时候,就要去想想有没有什么刁钻的数据。

2、G++的坑

真的很迷啊,一开始提交代码以后,C++成功AC了,G++依然WA.
尴尬的G++/C++编译器
根据以往的经验来看,G++总是容不下下面这句提高cincout效率的代码

ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

尤其是遇到字符串带空格输入的时候,G++编译器几乎100%出问题。

果不其然,把之前代码里cincout全部换成相应的scanfprintf之后,G++就也AC了(同样的代码C++自然也能AC)。

看来要求稳的话,以后还是少用cincout,多用scanfprintf吧……
汗

3、后话

这道题,我也是大意了,今天一路WA将近10次,况且一看到这道题目的时候,就有很明显的去年暑假做过的印象,而且印象中当时不到1小时就写完AC了,半年后的今天居然画上将近2小时时间,看来刷题是不能止步了,或许1天1道题都远远不够……

还记得当年高二时候教我数学的张老师说过

“许多题目,你会做,是因为你做过”

现在我也想补充一下

“许多题目,你知道怎么做,是因为你做过;你能很快做对,是因为你做多了”

平时多练练吧。没有足够的经验累积,如何应付新题?没有熟练的老题套路,如何腾出时间应付其余题目?
汗