• 2020.4.20 19:00-20:00

题目一

英雄打怪游戏。英雄和怪都有能力值，英雄只能打能力值小于自己能力值的怪，每打完一只怪获得一个金币，任意时刻可以用一个金币换取 1 点能力值，但金币数不能为负（初始为0）。问：英雄可以以随意顺序打怪，问拥有金币数的最大值，怪物可以不用打完。

>> 输入
1 3
2 2 1

• 说明：第一行第一个数表示英雄的初始能力值，第二个数表示怪物总数；第二行表示每个怪物的能力值

>> 输出
2

• 说明：英雄先打了能力值为 1 的怪物，把获得的 1 金币换成 1 点能力值，则现在有 2 点能力值，把剩下的怪物打完，总共获得 2 金币

做题结果： AC

思路：

1. 先对所有怪兽的能力值数组进行排序，从弱的开始打
2. 遍历排序后的所有怪兽，如果能力值够打就打完拿 1 金币，如果当前金币+能力值够打就打完拿 1 金币（金币和能力值进行更新）
3. 用一个值记录最大金币，每次用金币补贴之前先更新最大值
4. return 时再更新一次最大金币数

题目二

有 n 个城市，每个城市有一个等级值，这 n 个城市之间有 n-1 条边，每条边的时间权重都为 1，构成树结构。问：从任意城市到达另一个等级相同的城市，路径中不能有重复边，最小的时间是多少？（如果没有符合要求的路径，就返回 -1）

>> 输入
3
1 2 1
1 2
2 3

• 说明：第一行的数代表城市数 n，第二行代表每个城市的等级值，接下来的 n-1 行代表每条边的连接情况

>> 输出
2

• 说明：从城市 1 到城市 3，等级都为 1，经过时间是 2

做题情况： Fail

思路：

1. 处理输入花了很多时间
2. 时间不够，没有写完

希望做出来的大佬分享一下做法 orz