邯郸旅游景点,汕头seo服务,两学一做网站专栏,大连企业建站程序原题地址
解法一
排序贪心即可。思想为先计算出每一个怪兽到达城市的时间#xff0c;然后排序#xff0c;有小到大进行消灭#xff0c;此时的下标可视作时间。当怪兽到达城市的时间超过或等于当前时间时#xff0c;即已经到达了城市#xff0c;游戏失败#xff0c;下标…原题地址
解法一
排序贪心即可。思想为先计算出每一个怪兽到达城市的时间然后排序有小到大进行消灭此时的下标可视作时间。当怪兽到达城市的时间超过或等于当前时间时即已经到达了城市游戏失败下标即为消灭了多少个怪兽。O(nlogn) 时间复杂度主要在排序上。 int eliminateMaximum(vectorint dist, vectorint speed) {int length dist.size();vectorint times(length);for (int i 0; i length; i) {times[i] (dist[i] - 1) / speed[i] 1;}sort(times.begin(), times.end());for (int i 0; i length; i) {if (times[i] i)return i;}return length;}解法二
排序还是过于粗暴不优雅。进一步思考优化首先如果怪物到达的时间比怪物总数大可以忽略因为会尽可能先消灭到达时间快的怪物而在怪物总数的时间时已经可以把所有怪物消灭了。相较于排序这个解法不排序将怪物到达的时间计数然后从最小的开始进行怪物消灭。这时的下标不代表时间了需要额外使用变量记录当前时间。 int eliminateMaximum(vectorint dist, vectorint speed) {int length dist.size();vectorint times(length,0);for (int i 0; i length; i) {int time (dist[i] - 1) / speed[i] 1;if (time length) continue;times[time];}int time 0;for (int i 0; i length; i) {if(!times[i]) continue;if(timetimes[i]i) return i;time times[i];}return length;}
