记录编号	97653	评测结果	AAAAAAAAAA
题目名称	[UVa 11292] 勇者斗恶龙	最终得分	100
用户昵称	752199526	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2014-04-19 20:54:14	内存使用	0.34 MiB

#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<assert.h>
#include<time.h>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<cstring>
#include<functional>
#include<cctype>
using namespace std;
ifstream fin("DragonUVa.in");
ofstream fout("DragonUVa.out");
int main()
{
	int m,n,head[20001]={0},hero[20001]={0},money=0;//n-dragon;m-hero;
	//Step 1:Input and sort.===================================================================
	fin>>n>>m;
	for(int i=0;i<n;i++)fin>>head[i];sort(head,head+n);
	for(int i=0;i<m;i++)fin>>hero[i];sort(hero,hero+m);
	//Step 2:Greedy Algorithm.=================================================================
	if(n>m)fout<<"Loowater is doomed"<<endl;//Dragon can't be killed out.
	else if(head[n-1]>hero[m-1])fout<<"Loowater is doomed"<<endl;//Dragon can't be killed out.
	else
	{
		int i,j;
		for(i=0,j=0;i<n&&j<m;i++,j++)
		{
			if(hero[j]>=head[i]){money+=hero[j];head[i]=0;}//Dragon is be killed.
			else
			{
				while(hero[j]<head[i])j++;
				//Dragon is be killed.
				money+=hero[j];head[i]=0;
			}
		}
		for(int i=0;i<n;i++)
		{
			if(head[i]!=0){fout<<"Loowater is doomed"<<endl;return 0;}//Dragon hasn't been killed out.
		}
		fout<<money<<endl;//Dragon has been killed out.
	}
	return 0;
}