用户投稿HIHI，今天来分享个Google Code Jam 2018比赛的题目解法。不过因为时间的问题，所以我解完一题才会PO上来，所以这个系列大概会有四篇以上，还有因为其实我对C++不太熟，所以就用目前比较熟悉的JavaScript解出逻辑，希望各位大大不要介意。
首先是资格赛第一题「Saving The Universe Again(再次拯救宇宙)」：
故事背景是有个外星机器人在攻击宇宙，而我们必须阻止他。机器人的初始攻击力为1，攻击方式是使用一串指令做执行，指令由两个动作所组成第一个是「C(充电)」他会使机器人的攻击力翻倍，第二个是「S(射击)」机器人会以目前的攻击力做出等同数值的伤害。
举例来说，如果机器人的的指令是CSCCS，他所执行的动作会是以下：
1.C：充电，将初始攻击力1翻倍变为2
2.S：射击，将造成目前攻击力2点伤害
3.C：充电，将目前攻击力2翻倍变为4
4.C：充电，将目前攻击力4翻倍变为8
5.S：射击，将造成目前攻击力8点伤害
所以可以得知以上的指令共会造成10点伤害。
而现在的宇宙科学家有发明出一个能够承受伤害的盾牌，但是机器人的指令造成的伤害可能会比盾牌能够承受的伤害还高，所以在指令运行之前，我们能够去破解指令，让机器人造成的伤害能够让盾牌承受住并保护宇宙。破解的规则是交换相邻的指令，例如上述的CSCCS，他可以透过交换第一个和第二个指令来让指令变为SCCCS，如此一来就能让伤害从10减少为9，接着又可以再交换第四个和第五个指令变成SCCSC，这样又能让伤害从9减少为5，透过不断地破解让盾牌能够承受住机器人的伤害，不过为了避免机器人发现，破解的次数越少越好。
所以这一题求的是，在机器人的一串指令下，确保盾牌能够承受伤害的最少破解次数是多少？
输入的方式，第一行是指令数，接着输入的规则是盾牌血量和指令，以下例子：
3
1 CS
2 CS
1 SS
输出的结果为：
Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
第一个指令：盾牌血量为1，指令为CS，先充电再射击会让总伤害为2，所以透过把他们交换为SC，让伤害从2减少为1，成功抵挡攻击，因为交换了一次，所以是1。
第二个指令：盾牌血量为2，指令为CS，先充电再射击总伤害为2，因此不用交换盾牌就能承受了，所以是0次。
第三个指令：盾牌血量为1，指令为SS，不论怎么交换，总伤害都会是2，因此盾牌绝对承受不了这次攻击，所以是IMPOSSIBLE。
好的，那以下是我的程式码：
<html> <body> <!--透过textarea输入多行指令--> <textarea id="input" rows="10" cols="50"></textarea> <!--透过button执行事件--> <input type="button" value="送出" onclick="send()"/> <script> function send(){ //取得攻击指令 let word = document.getElementById('input').value; //总共有几行指令 let rowCount = word.split('\n').length-1; //用来装每次攻击的结果 let arrResult = new Array(); //开始读取指令(把盾的血量和攻击指令传到处理的函式) for(let i=1;i<=rowCount;i++){ //取这一行的开始和最后位置 let first = findIndex(word,'\n',i); let last = findIndex(word,'\n',i+1) || word.length; //撷取那一行的字串，开始撷取的地方+1才不会截到断行 let rowStr = word.slice(first+1,last); //把那行的字串用空白分割开来，因为前面是血量，后面是指令 let hp = rowStr.split(' ')[0]; let command = rowStr.split(' ')[1]; //送去判断能不能挡下这次攻击，然后要交换几次 arrResult[(i - 1)] = 'Case #' + i + ': ' + handleCommand(hp, command); //印出结果 console.log('Case #' + i + ': ' + handleCommand(hp, command)); } }; //处理指令 //hp:盾牌血量 command:攻击指令 function handleCommand(hp, command) { //先计算目前伤害值 let killValue = getKillValue(command); //计算次数 let count = -1; do { if (count === -1) { //第一次先单纯判断「有没有可能达成」或「有没有需要换位置」 //如果他目前伤害值小于盾的血量就不需要换 if (Number(killValue) <= Number(hp)) { return '0'; } //如果他的S的数量大于盾的血量就没不可能达成 if ((command.replace(/C/g, '')).length > Number(hp)) { return 'IMPOSSIBLE'; } count = 0; //下一次的迴圈就跑else } else { //第二次开始要换位置 count += 1; //先计算次数 //改变位置，让他去跑看看 command = revisionCommand(command); } } while (hp < getKillValue(command)); //如果总伤害量超过血量就继续跑迴圈 //过了以后回传次数 return count; }; //计算伤害值 //command:指令 function getKillValue(command) { //规则是 C:充电 S:射击 let killValue = 0; //总伤害量 let basedKill = 1; //目前伤害量 for (let i = 0; i <= command.length - 1; i++) { switch (command[i]) { case "C": { //集气 basedKill *= 2; break; }; case "S": { //加上目前伤害值 killValue += basedKill; break; }; }; }; return killValue; }; //改变指令 //command:当前攻击指令 function revisionCommand(command) { //规则是用最少的移动来让指令伤害不超过盾牌血量 //也就是说在C是充能和S是攻击的状况下，可以推出以下结论 //一、只要C后面没有S就等同不会造成更高的伤害，所以就在每一次交换的时候把C往S后面移动 //二、由于要在最少次数达成，所以优先处理最后出现的CS，因为CS出现在越后面代表伤害越高 //寻找指令中最后出现的CS然后将他们换位置 let lastCS = command.lastIndexOf('CS'); //把指令放进阵列中 let arrCommand = command.split(''); //把原本位置中的C换成S，S换成C arrCommand[lastCS] = 'S'; arrCommand[lastCS + 1] = 'C'; //把更改过位置的阵列转成字串后回传 return arrCommand.join(''); } //寻找字串 //str:被寻找的字串 findStr:要寻找的字串 findNum:要找第几个出现的字串 function findIndex(str, findStr, findNum) { //先取得第一次出现的位置 let index = str.indexOf(findStr); //之后去跑看要找第几次出现的地方 for (let i = 0; i < findNum - 1; i++) { //从上一次出现的地方开始找 index = str.indexOf(findStr, index + 1); } //如果是-1代表没找到就回传undefined if (index === -1) { index = undefined; } //回传最后一次出现的位置 return index; }; </script> </body></html>以上是我的程式码，结果如下：
因为我也没有其他指令能够测试到底正不正确了，所以如果以上有错误的地方，或是有哪里觉得怎么写会更好，再麻烦各位大大告诉我，我会尽速改进，谢谢大家。
微信扫一扫打赏
支付宝扫一扫打赏
