形式化题目

有 $N$ 个单位的牛奶需求，$M$ 个农民。第 $i$ 个农民的单位售价是 $P_i$，一天最多能卖 $A_i$ 个单位。牛奶完全同质，允许从一个农民那里只买一部分。数据保证所有农民的 总供给量不少于 $N$。

设从农民 $i$ 采购 $x_i$ 个单位，求

数据范围：$0 \leqslant N \leqslant 2\,000\,000$，$0 \leqslant M \leqslant 5\,000$， $0 \leqslant P_i \leqslant 1\,000$，$0 \leqslant A_i \leqslant 2\,000\,000$。 答案最大 $2 \times 10^9$，需要用 64 位整数存花费。

正解

思路

朴素想法。 直接模拟采购：每一步在尚有存货的农民里挑单价最低的那一位，能买多少买多少； 买光了他的库存就回去重新找下一个最低价，直到凑满 $N$。这个策略本身是对的（见下面的证明）， 但每次挑最低价都要扫一遍 $M$ 个农民，最坏要挑 $M$ 次，复杂度 $O(M^2)$， 在 $M = 5000$ 时约 $2.5 \times 10^7$ 次比较，虽然勉强能过，但大量比较是重复劳动。

瓶颈在哪？ 单价 $P_i$ 是输入给定、全程不变的常量，它不随采购过程变化。 也就是说"谁更便宜"这个次序在采购开始前就已经完全确定，模拟过程中一遍遍重新求最小值 是在反复计算同一个静态答案。既然如此，就没有必要动态地找最小值—— 事先排一次序即可。

贪心为什么正确？ 交换论证：设最优解中农民 $j$ 被采购了 $x_j > 0$ 个单位， 而某个单价更低（$P_i < P_j$）的农民 $i$ 还有剩余可卖量 $A_i - x_i > 0$。 把 $j$ 的 1 个单位挪给 $i$，总需求不变，总花费减少 $P_j - P_i > 0$，矛盾。 所以最优解一定优先用尽当前最便宜的可卖份额：

1. 只要农民 $i$ 还有货没买，就绝不去买任何单价比他贵的牛奶；
2. 因此所有农民被"用尽"的先后顺序，就是单价从小到大的顺序。

这两条合起来就是一句：按单价升序依次把每个农民的货拿光，直到需求被凑满。

算法步骤。

1. 把 $M$ 个农民的 $(P_i, A_i)$ 二元组按 $P_i$ 升序排序，$P_i$ 相同则顺序任意（牛奶同质）。
2. 记 remain = N，cost = 0，从头扫描排好序的序列：
   • 若 $A_i \leqslant$ remain：整批买下，cost += A_i * P_i，remain -= A_i；
   • 若 $A_i >$ remain：只买 remain 个单位，cost += remain * P_i，remain 归零后立即停止。
3. 输出 cost。

几个易错点。

• 最后一位必须截断：买的是 min(A_i, remain) 个单位，而不是把该农民的全部库存买光。
• 排序要按结构体整体排，不能只把价格数组排序而让供应量失去配对。
• 比较器用严格小于（P_i < P_j），写成 <= 会破坏严格弱序，在存在同价农民时行为未定义。
• $N = 0$ 的边界：需求为 0 时循环第一轮就不该买入，直接输出 0；把循环条件写成 remain > 0 即可自然处理。$M = 0$ 且 $N \geqslant 1$ 的情况由题面"总供给足够"排除。

以样例为例，输入 $N = 100$，五个农民的 $(P, A)$ 分别是 $(5, 20), (9, 40), (3, 10), (8, 80), (6, 30)$。按单价升序重排为

依次采购：买入 10 个 @3 花 30，剩 90；买入 20 个 @5 花 100，剩 70； 买入 30 个 @6 花 180，剩 40；轮到单价 8 的农民，只买 40 个凑满，花 320。 总计 $30 + 100 + 180 + 320 = 630$，与样例输出一致。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 07:03
# update_at: 2026-10-08 07:03

import sys


def greedy_cost(need: int, farmers: list[tuple[int, int]]) -> int:
    """按单价从低到高采购，返回凑满 need 加仑的最小花费。"""
    remain = need  # 还差多少牛奶没买到
    cost = 0       # 累计花费，量级 2e6 * 1000，Python 大整数天然安全
    for price, amount in sorted(farmers):  # 元组比较，主键就是单价
        if remain <= 0:
            break  # 需求已满足（含 need = 0 的边界）
        take = min(amount, remain)  # 剩下的第一个人只需买一部分
        cost += take * price
        remain -= take
    return cost


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    need, m = next(data), next(data)
    farmers = [(next(data), next(data)) for _ in range(m)]  # (价格 P_i, 供应量 A_i)
    print(greedy_cost(need, farmers))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 07:03
 * update_at: 2026-10-08 07:03
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 5005; // 农民数量上限

struct Farmer {
    ll price; // 每加仑牛奶的单价 P_i
    ll amount; // 该农民一天能提供的最大牛奶量 A_i
};

Farmer f[MAXM]; // f[1..m] 存每个农民的价格与供应量

// 按单价升序排序：单价相同时谁在前无所谓，牛奶完全同质
bool cmp_price(const Farmer &x, const Farmer &y) {
    return x.price < y.price;
}

int main() {
    ll need; // 每日需求量 N
    ll m;    // 农民数量 M
    if (scanf("%lld %lld", &need, &m) != 2) {
        return 0;
    }

    for (ll i = 1; i <= m; i++) {
        scanf("%lld %lld", &f[i].price, &f[i].amount);
    }

    sort(f + 1, f + m + 1, cmp_price);

    ll remain = need; // 还差多少牛奶没买到
    ll cost = 0;      // 累计花费，最坏 2e6 * 1000 = 2e9，必须用 64 位
    for (ll i = 1; i <= m && remain > 0; i++) {
        if (f[i].amount <= remain) {
            // 该农民的牛奶全部买下还不够（或刚好够），整批拿走
            cost += f[i].amount * f[i].price;
            remain -= f[i].amount;
        } else {
            // 只买凑满需求的那一部分，买完就结束
            cost += remain * f[i].price;
            remain = 0;
        }
    }

    printf("%lld\n", cost);
    return 0;
}

复杂度

• 时间：排序 $O(M \log M)$，扫描 $O(M)$（每位农民 $O(1)$ 次算术），总计 $O(M \log M)$。 $M = 5000$ 时排序比较约 $6 \times 10^4$ 次，远小于 1000 ms 的限制。
• 空间：只需存 $M$ 个 $(P_i, A_i)$ 二元组，$O(M)$，约几十 KB，远低于 128 MB 限制。
• 与 C++ 解法的关系：main.py 与 main.cpp 是同一算法的两个语言版本—— 两者都是"排序 + 线性扫描"，复杂度同为 $O(M \log M) + O(M)$。 Python 侧用 sorted() 排元组（元组比较默认以价格为主键）以及 min(amount, remain) 表达截断，写法更短但语义完全一致；本题数据量下 Python 也没有 TLE 风险。

总结

• 静态的次序不要动态求：当决策依据（这里是单价）不随时间改变时，先排序再线性扫描， 就能把朴素做法的 $O(M^2)$ 降到 $O(M \log M)$。
• 贪心的正确性靠交换论证：把"用更贵的牛奶"换成"用更便宜的牛奶"总能降低成本， 因此最优解必然优先用尽最便宜的份额。牛奶连续可拆、单价恒定，是这一步成立的前提。
• 最后一位要截断：只有能整批拿下的农民才买光，第一个超过剩余需求的农民只取所需部分。
• 答案 64 位：$N \times P_{\max} = 2 \times 10^9$ 已经逼近 int 上界， C++ 侧必须用 long long 累计花费。