简单的贪心算法

题目：Mixing Milk（usco76）

问题描述：

某商人欲从M个农民那里购买N公斤牛奶。给定整数M，N及若干个农民拥有牛奶的价格和总量。问他最少需要多少钱可以购买N公斤牛奶

v     Sample Input:

100 5         //商人要买的牛奶量和总共有的农民数(N,M)

5 20          //以下５行，是每个农民的牛奶单价和他有的牛奶总量

9 40

3 10 

8 80

6 30

v     Output:

630                    //花的最少钱

用贪心法的关键是找到最优的度量标准。既然本题要求花钱最小，我们就可以选择牛奶的价格为度量标准。这是个简单的贪心算法：商人想花最少钱买牛奶，肯定是先挑便宜的买，把最便宜的买光了，还不够量的话，就去买次便宜的……直到数量够了为止。

源程序如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct intpair
{
 intpair(int a=0,int b=0)
 {
  price=a;
  num=b;
 }//intpair
 int price,num;//价格和数量
} ;

bool small(intpair v1,intpair v2)//为sort写的小函数
{
 return  v1.price<v2.price;
}//small

int cost(vector<intpair>&V,int N)
{
 sort(V.begin(),V.end(),small);//先按价格排序
 int result=0,i=0,already=0;
 while(V[i].num+already<N)　//按贪心原则最优化
 {
  already+=V[i].num;
  result+=V[i].num*V[i].price;
  i++;
 }//while
 return result+V[i].price*(N-already);//把剩下的搞掂
}//cost
int main()
{
 int M,N,price,num;
 vector<intpair> V;
 V.reserve(3000);
 cin>>N>>M;
 for(int i=0;i<M;i++)
 {
  cin>>price>>num;
  V.push_back(intpair(price,num));
 }//for
 cout<<cost(V,N)<<endl;
 return 0;
}//main