uva - 11292 - Dragon of Loowater（贪心）

题意：（搬自lrj大大的书）你的国王里边有一条n个头的恶龙，你希望雇佣一些骑士把它杀死，（砍掉所有的头）。村里有m个骑士可以雇佣，一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头，且需要支付x个金币。要砍掉所有的头，且支付金币最少。

方法：对头的直径和骑士的能力值排序，比较即可。贪心算法。

#include <iostream>  
#include <iomanip>  
#include <string>  
#include <cstring>  
#include <cstdio>  
#include <queue>  
#include <stack>  
#include <algorithm>  
#include <cmath>  

using namespace std;

#define MAX 20000+10
int head[MAX], warrior[MAX], n, m, sum;

void Input()
{
	int i = 0, j = 0;
	for (i = 0; i < n; i++)
		cin >> head[i];
	for (i = 0; i < m; i++)
		cin >> warrior[i];
}

void Calulate()
{
	int i = 0, j = 0;
	while (j < m)
	{
		if (warrior[j] >= head[i])
		{
			sum += warrior[j], i++, j++;
		}
		else
		{
			j++;
		}
		if (i == n)
		{
			cout << sum << endl;
			return;
		}
	}
	cout << "Loowater is doomed!" << endl;
}

int main()
{
#ifdef Local  
	freopen("a.in", "r", stdin);  
#endif  
	int i = 0, j = 0;
	while (cin >> n >> m && n+m)
	{
		memset(head, 0, sizeof(head));
		memset(warrior, 0, sizeof(warrior));
		sum = 0;
		Input();
		sort(head, head+n);
		sort(warrior, warrior+m);
		Calulate();
	}
}

uva - 11292 - Dragon of Loowater（贪心）

原文：http://blog.csdn.net/u013545222/article/details/19073629