洛谷题单指南-贪心-P1208 [USACO1.3] 混合牛奶 Mixing Milk

原题链接：https://www.luogu.com.cn/problem/P1208

题意解读：就是一个部分背包问题，贪心模版题。

解题思路：优先选择单价低的牛奶即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 5005;

struct farmer
{
    int price, count;
} f[N];

bool cmp(farmer f1, farmer f2)
{
    return f1.price < f2.price;
}

int n, m;
int ans;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> f[i].price >> f[i].count;
    sort(f + 1, f + m + 1, cmp);

    int i = 1;
    while(n)
    {
        if(n > f[i].count)
        {
            ans += f[i].price * f[i].count;
            n -= f[i].count;
        }
        else
        {
            ans += f[i].price * n;
            n = 0;
        }
        i++;
    }
    cout << ans;

    return 0;
}