本题是USACO提供的贪心+结构体的题。
先逐步分析题目:
【题干】
Marry 乳业想采购一些牛奶,找到了几位奶农,用奶农提供的数据,来计算采购足够数量的牛奶所需的最小花费。
【输入】
第一行二个整数 n,mn,mn,m,表示需要牛奶的总量,和提供牛奶的农民个数。
接下来 mmm 行,每行两个整数 pi,aip_i,a_ipi ,ai ,表示第 iii 个农民牛奶的单价,和农民 iii 一天最多能卖出的牛奶量。
【输出】
输出最小金额。
【数据】
0≤n,ai≤2×106,0≤m≤5×103,0≤pi≤1030≤n,a_i≤2×10^6,0≤m≤5×10^3,0≤p_i≤10^30≤n,ai ≤2×106,0≤m≤5×103,0≤pi ≤103。
分析完成后,再将思路分享给大家:
可以先定义一个结构体,存单价和提供总数。
再对单价进行升序排序。
最后进行贪心。
贪心时的注意事项:
> 1.注意while的结束条件
> 2.注意最后的特判环节(早代码里会提到)
接下来就是心心念念的 codecodecode 环节
要个赞不过分吧?