FatMouse' Trade
Problem Description
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.
Input
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.
Output
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.
Sample Input
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1
Sample Output
13.3333
1.500
Author
CHEN, Yue
Source
题目类型：贪心
算法分析：直接算出每一种物品的价值/花费，然后按其从大到小排序。最后对于给定的背包的容量，尽量将单位价值高的物品放入。注意本题的坑点是精度！！！！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 66600 + 66; struct Node { double v, w; double avr; }; Node ans[maxn]; bool Cmp (Node a, Node b) { return a.avr > b.avr; } int main() { // ifstream cin ("aaa.txt"); int n, m; while (cin >> m >> n) { if (m == -1 && n == -1) break; int i; for (i = 0; i < n; i++) { cin >> ans[i].v >> ans[i].w; ans[i].avr = ans[i].v * 10.0 / ans[i].w / 10; } sort (ans, ans + n, Cmp); double sum = 0; i = 0; while (i < n && m - ans[i].w >= 1e-5) { sum += ans[i].v; m -= ans[i].w; i++; } if (i < n) sum += ans[i].avr * m; printf ("%.3lf\n", sum); } return 0; } |
- « 上一篇：hdu1005
- hdu1023：下一篇 »