网站建站网站微信公众号开发,泰安今天最新招聘信息,天津网站的优化,厚街建设网站一、题目分析
需要满足的条件#xff1a;
只能在每分钟的开始使用武器武器能杀死距离城市最近的怪兽怪兽到达城市就会输掉游戏
游戏最优策略#xff1a;我们可以在每分钟的开始都使用一次武器#xff0c;用来杀死距离城市最近的怪兽。这样可以在力所能及的范围内#xf…一、题目分析
需要满足的条件
只能在每分钟的开始使用武器武器能杀死距离城市最近的怪兽怪兽到达城市就会输掉游戏
游戏最优策略我们可以在每分钟的开始都使用一次武器用来杀死距离城市最近的怪兽。这样可以在力所能及的范围内杀死最多的怪兽。
二、测试用例分析 示例1中打怪兽的策略可以打死 3只怪兽其实也可以换成这样的打法
第 0 分钟开始时怪物的距离是 [1,3,4]你消灭了第一个怪物。第 1 分钟开始时怪物的距离是 [X23]你消灭了第二个怪物。第 2分钟开始时怪物的距离是 [XX2]你消灭了第三个怪物。所有三个怪物都可以被消灭。
注意我认为示例1中的方法不是“最优”策略。另外大家不要被这个示例误解看第二步的时候竟然没有消灭任何怪物会误认为只有怪物和城市距离为1才能打死怪物或者误认为只有在第i分钟内才能到达的怪物才可以在i分钟时消灭。
三、解题策略
我们可以计算每一个怪物最晚被消灭的时间然后对时间进行排序。可以晚点消灭的怪物就会被排到后面。
例如dist4speed2
第 0 分钟开始时怪物的距离是4可以暂时不消灭第 1 分钟开始时怪物的距离是2如果这时候不消灭的话第2分钟开始时怪物就到达城市游戏失败了。因此最晚消灭时间timedist/speed-11
例如dist5speed2
第 0 分钟开始时怪物的距离是5可以暂时不消灭第 1 分钟开始时怪物的距离是3可以暂时不消灭第 2 分钟开始时怪物的距离是1如果这时候不消灭的话第3分钟开始时怪物就到达城市游戏失败了。因此最晚消灭时间timedist/speed2
总结
若dist%speed0timedist/speed-1否则timedist/speed
四、示例代码
class Solution {
public:static bool cmp(int a,int b){return ab;}int eliminateMaximum(vectorint dist, vectorint speed) {vectorint time;for(int i0;idist.size();i){if(dist[i]%speed[i]0){time.push_back(dist[i]/speed[i]-1);}else{time.push_back(dist[i]/speed[i]);}}sort(time.begin(),time.end(),cmp);int sum0;for(int i0;itime.size();i){if(itime[i]){sum;}else{break;}}return sum;}
};
