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 txinline 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 txtfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifwhile (~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;
}