今天开始认真做的白书的第一题(The Dragon of Loowater),觉得其实认真来分析下题目的确有思路之后就没有很大问题了。
这题主要用到了排序和贪心算法,每次比较相同位置骑士的能力值和恶龙头的直径大小,如果可以砍就雇佣,不可以就抛弃继续换下一个骑士能力值和龙头进行比较,感觉和
树里面选取最短路的方法有点像。
感想其实也没多少,废话不多说,贴代码:<代码风格很烂,而且第一次用C++还不怎么会,要改进啊啊啊啊啊啊啊啊啊啊啊啊啊啊,这份代码借鉴了书上的模式,但是基本以自己理解写的>
#include<iostream> #include<stdio.h> #include <algorithm> using namespace std; #define maxn 20000 + 5 int main(void) { int Dragon[maxn], Loowater[maxn]; int i, n, m; while(scanf("%d%d", &n, &m) == 2 && n && m) //循环输入这一点一定要学会啊啊啊啊啊啊啊啊 { for(i = 0; i < n; i++) scanf("%d", &Dragon[i]);//输入恶龙头的直径 for(i = 0; i < m; i++) scanf("%d", &Loowater[i]);//输入骑士能力值 sort(Dragon, Dragon+n); sort(Loowater, Loowater+m); int cur = 0; int cost = 0; for(i = 0; i < m; i++) { if(Loowater[i] >= Dragon[cur]) //比较恶龙头直径和骑士能力值 { cost += Loowater[i]; //骑士能力值大于龙头直径则雇佣 if(++cur == n) break; //砍龙完毕结束循环 } } if(cur < n) printf("Loowater id doomed! "); else printf("%d ", cost); } return 0; }