贪心算法例题：2850商人小鑫

Problem Description

小鑫是个商人，当然商人最希望的就是多赚钱，小鑫也一样。
这天，他来到了一个遥远的国度。那里有着n件商品，对于第i件商品需要付出ci的价钱才能得到。当然，对于第i件商品，小鑫在自己心中有一个估价pi：代表着当他买下这件商品后带回他的国家可以卖出的价格。小鑫只能带回m件商品，你能帮他计算一下他最多能赚多少钱么？
Input

输入有多组，到文件结束。（注：数据有很多组，请用高效率算法）
对于每一组数据。第一行是n，m。m≤n≤10000000。
紧接着有n行，每一行有两个数 c ，p。第i行代表着ci，pi。ci≤pi
数据都在int范围内 。  
Output

对于每组输入数据只输出一行一个数，代表小鑫能赚多少钱。
Example Input

4 2
1 2
1 3
2 2
3 4
Example Output

3

这道题和买大米、装船问题相似，而且我还会做，可以说相当简单了。

这道题大体的意思就是出国买东西回来再倒卖，有n个货物你可以买，但只能带走m个货，还必须保证带走的m个货倒卖获得的利润最大。当想到这个最大的时候，就想到我刚刚学到的贪心算法。

大体思路：按货物赚的中间价排序，选走m个中间价格最大的。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 10000001
struct node{
	int c;//买价 
	int p;//卖价
	int x;//可赚的钱 
}Goods[N];
int cmp(node a,node b){
	return a.x>b.x;
}
int main(){
	int n,m;
	int i;
	while(scanf("%d%d",&n,&m)!=EOF){
		int sum=0;
		for(i=0;i<n;i++){
			scanf("%d%d",&Goods[i].c,&Goods[i].p);
			Goods[i].x=Goods[i].p-Goods[i].c;
		}
		sort(Goods,Goods+n,cmp);
		for(i=0;i<m;i++){
			sum=sum+Goods[i].x;
		}
		printf("%d
",sum);
	}
	return 0;
}