本文共 1000 字,大约阅读时间需要 3 分钟。
这道题很简单的贪心算法,写到这里只是为了总结一下
C++ 中map可以简单地实现排序和联系两组数
这里唯一值得注意的地方是map.insert()这个方法在key已存在的情况下并不插入,所以得看一下返回值,如果插入失败,就更改key所关联的值。
/*
ID:thestor1
PROG:milk
LANG:C++
*/
#include <iostream>
#include <fstream>
//#include <utility>
#include <map>
using namespace std;
int main()
{
ifstream is("milk.in");
int N,M;
is>>N>>M;
map<int,int> milk;
for(int ix=0;ix<M;++ix)
{
int price,amount;
is>>price>>amount;
pair<map<int,int>::iterator,bool> ret=milk.insert(make_pair(price,amount));
if(!ret.second)
ret.first->second+=amount;
}
is.close();
//ofstream save("save.txt");
//for(map<int,int>::iterator iter=milk.begin();iter!=milk.end();++iter)
//{
//save<<iter->first<<" "<<iter->second<<endl;
//}
//save.close();
int tPrice=0,tAmount=0;
map<int,int>::iterator iter=milk.begin();
while(tAmount<N)
{
if(N-tAmount>iter->second)
{
tPrice+=iter->first*iter->second;
tAmount+=iter->second;
}
else
{
tPrice+=iter->first*(N-tAmount);
tAmount=N;
}
++iter;
}
ofstream os("milk.out");
os<<tPrice<<endl;
os.close();
return 0;
}
转载地址:http://stxli.baihongyu.com/