USACO1.3 Mixing Milk(milk)
837 ワード
最も簡単な貪欲な戦略の問題は、multimapを使って価格が低いから高い順に、最低価格の牛乳を順番に買って、買えるまで買います.
/*
ID:jzzlee1
PROG:milk
LANG:C++
*/
#include <fstream>
#include<iostream>
#include<map>
#include<utility>
#include<cstring>
using namespace std;
ifstream fin("milk.in");
ofstream fout("milk.out");
int main()
{
int n,m;
fin>>n>>m;
multimap<int,int> maps;
int x,y;int i;
for(i=0;i!=m;i++)
{
fin>>x>>y;
maps.insert(make_pair(x,y));
}
multimap<int,int>::iterator it;
int sum=0,money=0;
for(it=maps.begin();sum!=n;it++)
{
if(n-sum>it->second)
{
sum+=it->second;
money+=it->first*it->second;
}
else
{
money+=it->first*(n-sum);
sum=n;
}
}
fout<<money<<endl;
return 0;
}