一、The Dragon of Loowater【UVa11292】

1.题意： 国王要杀恶龙， 需要雇佣骑士。 每个骑士只能杀一条龙。 当骑士能力 不小于 龙头直径时， 骑士可以砍下龙头。 雇佣骑士需要钱， 钱就等于他的能力。 如果骑士能成功砍下所有的龙头， 则输出雇佣总费最少的数值， 否则输出那句鸟语。

 

2.这是一道很典型的贪心题，只要骑士有能力（大于等于头的直径就可以砍头），但是如果要让一个能力大的去砍一个头直径小的龙，会浪费很多得钱，所以要想让钱最少，就要让骑士的能力刚好得到充分利用，也就是尽可能的不浪费。

 

3.所以代码【Vector初学者只想练习一下】

#include <cstdio>//n为头的直径，m为骑士能力
#include  <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int INF=1e9;
int main()
{
	vector<int>v1;//v1为头的直径 
	vector<int>v2;//v2为骑士能力 
	int m,n;
	while(scanf("%d%d",&m,&n)&&m&&n)
	{
		int x,y;
		for(int i=1;i<=m;i++)
		{
			scanf("%d",&x);
			v1.push_back(x);
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x);
			v2.push_back(x);
		}
		sort(v1.begin(),v1.end());
		sort(v2.begin(),v2.end());
		x=v1.size();
		y=v2.size();
		int cur=0,flag=0;
		int sum=0;
		for(int i=0;i<y;i++)
			if(v2[i]>=v1[cur])
			{
				sum+=v2[i];//雇佣该骑士
				if(++cur==x) break;//已经将所有的砍完
			}
		if(cur==x)
			printf("%d\n",sum);
		else
			printf("Loowater is dcomed!\n");
	}
	return 0;
}

 

二、Commando War【UVa11729】

1.题目大意：有n个人要去执行任务，第i个人交代任务的时间为Bi，了解完任务之后会不间断的执行Ji分钟，完成所有任务的最短时间，两个人不能同时交代任务，但可以同时执行任务。

 

2.我们贪心的性质是什么，我们不妨画图检测一下：

1.假设交代时间相同，如果执行时间长的在前

交代时间  ***   执行时间++

***++++        如果执行时间长的在后        ***+++

    ***+++                交换                               ***++++

很明显执行时间长的在后耗用时间多！【【前者长度为8，后者长度为9】

 

2.所以这道题的贪心性质为：根据执行时间的长短排序。

 

#include <cstdio>//n为头的直径，m为骑士能力
#include  <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int INF=1e9;
struct T{
	int carry;
	int roger;
};
bool operator<(T a,T b)//重载T中的运算符 
{
	return a.carry>b.carry;
}
int main()
{
	int m,n;
	vector<T>v; 
	while(scanf("%d",&n)&&n)
	{
		int x,y;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&x,&y);
			v.push_back({y,x});
		}
		sort(v.begin(),v.end());//根据重载运算符进行排序 
		int sum=0,ans=-INF;//sum记录交代时间，ans更新最晚完成时间
		x=v.size();
		for(int i=0;i<x;i++)
		{
			sum+=v[i].roger;
			ans=max(ans,sum+v[i].carry);	
		} 
		//完成第一个任务需要V[1].roger+v[1].carry
		//完成第二个任务需要v[2].roger+v[1].roger+v[2]carry
		//因为完成任务时有重复的时间，所以只需要保留最长的时间即可 
		printf("%d\n",ans);
	}	
	return 0;
}

三、补充

1.Vector是一个不定长数组，可以节省内存空间，但本次比较繁琐，例如第一个题可以用普通数组做。但写这个两个题的目的是为了练习Vector的使用，与贪心算法，所以用了Vector。

2.另外，第一个题，本来我的思路为O（n^2)的复杂度，即都从小到大排序之后，从骑士能力数组中用二分查找lower_bound查找大于等于其能力的第一个数，再加上。突然一想，其实完全可以用On解决，具体即为上述代码，自己想一下即可，过多不再解释。

3.小年将至，大家新年快乐！