[USACO1.3] 混合牛奶 Mixing Milk

GitHub跳转原题关系图返回列表

按单价从低到高购买牛奶，每次尽量买满当前最便宜农民的供应量。

OJ: luogu

题目 ID: P1208

难度:入门

标签:贪心排序python

日期: 2026-07-15 22:15

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

需要购买 N 单位牛奶，有 M 个农民。每个农民给出单价 P_i 和最多能卖的数量 A_i。总供应量保证足够，求买够 N 单位牛奶的最小花费。

思路

每单位牛奶没有区别，只是价格不同。因此越便宜的牛奶越应该优先买。

如果某个方案先买了更贵的牛奶，同时还剩下更便宜的牛奶没买，那么把这部分购买量换到便宜农民那里，总数量不变，花费只会下降。所以最优方案一定可以按单价从低到高购买。

做法：

  1. 把农民按单价排序；
  2. 从低价到高价扫描；
  3. 当前农民能买多少就买多少，但不能超过剩余需求；
  4. 需求变成 0 时结束。

Python 知识

  • farmers.append((price, amount)) 用元组保存一条记录。
  • farmers.sort() 会先按单价排序，单价相同再按数量排序；本题单价相同的顺序不影响答案。
  • min(need, amount) 表示当前最多购买量。

这是典型排序贪心题，跳过 brute.py，用样例和交换论证说明正确性。

代码

python
import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    need, farmer_count = data[0], data[1]

    farmers = []
    pos = 2
    for _ in range(farmer_count):
        price, amount = data[pos], data[pos + 1]
        pos += 2
        farmers.append((price, amount))

    farmers.sort()

    answer = 0
    for price, amount in farmers:
        buy = min(need, amount)
        answer += buy * price
        need -= buy
        if need == 0:
            break

    print(answer)


if __name__ == "__main__":
    main()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P1208 [USACO1.3] 混合牛奶 Mixing Milk */
/* 按单价从低到高购买，每次尽量买满当前最便宜农民的供应量。 */

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

const int MAXM = 5005;

int need, farmer_cnt;
// 农民信息：单价和供应量
int price[MAXM], amount[MAXM], idx[MAXM];

bool cmp(int a, int b) {
    return price[a] < price[b]; // 按单价升序
}

int main() {
    cin >> need >> farmer_cnt;
    for (int i = 1; i <= farmer_cnt; i++) {
        cin >> price[i] >> amount[i];
        idx[i] = i;
    }

    sort(idx + 1, idx + farmer_cnt + 1, cmp);

    int ans = 0;
    for (int i = 1; i <= farmer_cnt && need > 0; i++) {
        int id = idx[i];
        // 当前农民最多能买多少
        int buy = min(need, amount[id]);
        ans += buy * price[id];
        need -= buy;
    }

    cout << ans << "\n";
    return 0;
}

复杂度

排序复杂度是 O(Mlog⁡M)O(M \log M)，扫描复杂度是 O(M)O(M)。

空间复杂度是 O(M)O(M)。

总结

当每个单位物品没有差异，只是购买价格不同，最小花费通常就是按单价升序贪心购买。