天天看點

例題1:勇士鬥惡龍

題目:你的王國裡有一條n個頭的惡龍,可以雇傭騎士把它殺死,村裡有m個騎士,能力值為x的騎士可以砍掉一個惡龍直徑不超過x的頭,且需支付金币x,怎樣才能殺死惡龍并且支付金币最少?(一個騎士隻能砍一個頭,雇傭一次)

#include <iostream>
using namespace std;
void main()
{
	//這裡偷懶不輸入了,a[]表示惡龍的頭的直徑,b[]表示騎士的能力值
	//int a[2]={5,5},b[1]={10};
	int a[2]={5,4},b[3]={7,8,4};
	int min=0,temp;
	bool flag;//flag用于标記是否完成任務
    for(int i=0;i<2;++i){
		temp=1000;
		flag=0;
		for(int j=0;j<3;++j){
			if(b[j]>=a[i] && b[j]<temp){
				temp=b[j];
				flag=1;
				b[j]=0;//如果雇傭,則能力值清空,防止重複雇傭
			}
		}
		if(0==flag){
			cout<<"Loowater is doomed"<<endl;
			break;
		}
		else
		min+=temp;
	}
    if(1==flag)
		cout<<min<<endl;
	system("pause");
}
           

繼續閱讀