hdu1009 FatMouse‘ Trade贪心

FatMouse’ Trade 猫有$M$个猫粮，然后每次可以用$f[i]\ast a\%$的猫粮去换$j[i]\ast a\%$的咖啡豆，然后问你最多可以获得多少咖啡豆。

一个贪心问题，按性价比来换，如果$1$猫粮换的咖啡豆最多，那我们就换，以此类推。

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; typedef long long ll; const int N = 1e3 + 10; const int M = 1e5 + 10; const int INF = 0x3f3f3f3f; #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define pb(x) push_back(x) #define mem(x, a) memset(x, a, sizeof(x)); #define endl '\n' #define ls (i << 1) #define rs (i << 1 | 1) #define loop(i, a, b) for (int i = a; i < b; ++i) #define tx inline int read() { char ch = getchar(); int w = 1, c = 0; for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) c = (c << 3) + (c << 1) + (ch ^ 48); return w * c; } int n, m; struct node { int j, f; double x; } a[N]; bool cmp(node xx, node yy) { return xx.x > yy.x; } int main() { #ifdef txt freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif while (~scanf("%d%d", &m, &n)) { if (m == -1 && n == -1) break; for (int i = 0; i < n; ++i) { scanf("%d%d", &a[i].j, &a[i].f); a[i].x = 1.0 * a[i].j / a[i].f; } sort(a, a + n, cmp); // 按性价比排序 double ans = 0.0; for (int i = 0; i < n; ++i) { if (m >= a[i].f) { // 能全换 ans += a[i].j; m -= a[i].f; } else { // 不能全换 ans += a[i].x * m; break; } } printf("%.3f\n", ans); } return 0; }