USACO Mixing Milk 题解
/*ID: bbsunch2PROG: milkLANG: 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（计数排序）的条件，在算法导论的第八章有描述，非常简单。

而说到计数排序，就不得不谈谈排序算法的稳定性问题，选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。具体分析参考百度即可。

?