Milk Procurement / 牛奶采购

版权信息： usaco美国信息学奥赛

任务总览

题目描述

由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。请帮助 Marry 乳业找到最优的牛奶采购方案。

Marry 乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格是不同的。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。

给出 Marry 乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。

注： 每天所有奶农的总产量大于 Marry 乳业的需求量。

输入格式

第一行包含两个整数 n, m，分别表示 Marry 乳业所需的牛奶总量，以及提供牛奶的农民数量。  
接下来 m 行，每行包含两个整数 pi, ai，分别表示第 i 个农民的牛奶单价，以及该农民每天最多能供应的牛奶量。

输出格式

输出一个整数，表示采购足够数量的牛奶所需的最小花费。

输入输出示例

输入示例 1

100 5
5 20
9 40
3 10
8 80
6 30

输出示例 1

630

题目分析

1. 目标： 选择购买牛奶的方案，使得总采购成本最小，并且能够满足 Marry 乳业的需求量。
2. 思路：
   • 优先从价格最低的农民处购买牛奶，以确保总成本最小。
   • 采用贪心策略，按照牛奶单价 pi 从小到大排序，然后依次购买，直到满足需求 ​n​。
   • 如果某个农民的牛奶不足以满足剩余需求，就尽可能多买；如果足够，则只购买所需的部分。
3. 优化：
   • 先对农民按照 pi 进行排序，然后依次遍历，逐步计算最小采购成本。
   • 由于 ​m ≤ 5000​，排序的复杂度 O(m log m) 可接受，总体复杂度为 ​**O(m log m + m) ≈ O(m log m)**​。

时间复杂度分析