hdu1009 FatMouse‘ Trade贪心

FatMouse’ Trade

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

一个贪心问题，按性价比来换，如果 1 1 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;
}