小毛的交易

题目描述
​ 小毛准备了 M 磅的猫咪食物去和猫咪交易他最喜欢的食物爪哇豆。猫咪有 N 间仓库，其中第 i 间仓库包含着 s[i] 磅的爪哇豆，但要花费 f[i] 磅的猫咪食物去和他们交换。小毛很聪明，经过他的各种交换，发现自已没有必要把每一个仓库的食物全部买下，他可以偷偷地买下一部分。也就是说，他可以获得 s[i]∗a 磅的爪哇豆而只花费 f[i]∗a 磅的猫咪食物。但是，他不知道该怎么买才能买到最多的爪哇豆。请帮他计算一下。

输入
​ 第一行有两个整数 M,N。

接下来的 N 行，每行两个非负整数 s[i],f[i]。

注：所有整数不超过 1000。

输出
​ 输出一个实数，保留小数点后三位，表示小毛最多能买到多少磅的爪哇豆。

样例输入
5 3
7 2
4 3
5 2
样例输出
13.333
数据规模与约定
​ 时间限制：1 s

内存限制：256 M

100% 的数据保证 N,M≤1000

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

struct node {
    double val, cost, num;
};

bool cmp(node a, node b) {
    return a.num > b.num;
}

double m, n, ans;
node s[1005];

int main() {
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i].val >> s[i].cost;
        s[i].num = s[i].val / s[i].cost;
    }
    sort(s, s + (int)n, cmp);
    for (int i = 0; i < n; i++) {
        if (m <= s[i].cost) {
            ans += s[i].num * m;
            break;
        }
        ans += s[i].val;
        m -= s[i].cost;
    }
    printf("%.3f\n", ans);
    return 0;
}