题目大意:
描述
由于乳制品产业利润很低,所以降低原材料(牛奶)价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。
Marry乳业从一些奶农手中采购牛奶,并且每一位奶农为乳制品加工企业提供的价格是不同的。此外,就像每头奶牛每天只能挤出固定数量的奶,每位奶农每天能提供的牛奶数量是一定的。每天Marry乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。
给出Marry乳业每天对牛奶的需求量,还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。
注:每天所有奶农的总产量大于Marry乳业的需求量。
格式
PROGRAM NAME: milk
INPUT FORMAT:file milk.in
第 1 行共二个数值:N,(0<=N<=2,000,000)是需要牛奶的总数;M,(0<= M<=5,000)是提供牛奶的农民个数。
第 2 到 M+1 行:每行二个整数:Pi 和 Ai。
Pi(0<= Pi<=1,000) 是农民 i 的牛奶的单价。
Ai(0 <= Ai <= 2,000,000)是农民 i 一天能卖给Marry的牛奶制造公司的牛奶数量。
OUTPUT FORMAT:file milk.out
单独的一行包含单独的一个整数,表示Marry的牛奶制造公司拿到所需的牛奶所要的最小费用
以上内容来自NOCOW
这一题太明显的贪心了,然后把价格排序就可以了。那排序呢,STL提供了map可以完美兼容这种操作,当然网上也有用struct自己来实现的,我要说,效率不一定高嘛,因为印象中map是用堆排序来实现的
但是这一题真的卡住了一下,因为map在重复键值的情况下是不能插入的,哦,insert,所以当农民的价格相等时,如果不加判断,就会出错的!
下面是可以通过的源码:
/* ID: bbsunch2 PROG: milk LANG: C++ */ #include <iostream> #include <fstream> #include <string> #include <vector> #include <stdlib.h> #include <map> using namespace std; int main() { ofstream fout ("milk.out"); ifstream fin ("milk.in"); map<int, int> price_farmerAmount; int totalAmount = 0; int farmerNum = 0; int totalPrice = 0; fin >> totalAmount >> farmerNum; for(int i = 0; i < farmerNum; i++) { int price; int farmerAmount; fin >> price >> farmerAmount; pair<map<int,int>::iterator,bool> ret = price_farmerAmount.insert(pair<int, int>(price, farmerAmount)); if(!ret.second) { ret.first->second += farmerAmount; } } map<int, int>::iterator it; for( it = price_farmerAmount.begin(); it != price_farmerAmount.end(); it++) { int price = it->first; int farmerAmount = it->second; if(totalAmount > farmerAmount) { totalPrice = totalPrice + price * farmerAmount; totalAmount -= farmerAmount; }else { totalPrice = totalPrice + price * totalAmount; break; } } fout << totalPrice << endl; return 0; }
有人问为什么要维护USACO题解这个系列,因为,USACO是不会帮你保存源码的,骚年
这一题有个很trick的技巧,也是USACO给出的题解,就是排序可以再O(n)复杂度下完成,因为这个排序满足count sort(计数排序)的条件,在算法导论的第八章有描述,非常简单。
而说到计数排序,就不得不谈谈排序算法的稳定性问题,选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。具体分析参考百度即可。
相关推荐
USACO所有题目的题解 NOCOW整理版
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
USACO月赛题解1
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco第五章milk4的解题代码,供算法初学者参考
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
丰富的USACO1.1--2.3.4的所有题解
非常详细的题解,个人觉得很好,帮助非常大。nocow关闭后不太好找资源了。
非常详细的题解,比较全的,个人觉得刷题者可以入手,帮助非常大。
非常详细的题解,比较全的,个人觉得刷题者可以入手,帮助非常大。
非常详细的题解,个人觉得比较全的,刷题者可以入手,帮助会非常大。
我的USACO题解和程序
USACO题解(NOCOW整理版).doc
usaco全部题解。 网址:blog.csdn.net/jiangshibiao
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写
里面有usaco前几节的程序和代码,欢迎使用,希望对你有所帮主。
usaco的某道题的题解
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
USACO(即美国高中生的编程竞赛网站)中的 pprime 题的题解
数据结构机考所参考的USACO网站所有题目的解题思路,资源比较稀有!