摘要：使用若干次物理攻击和至多一次魔法攻击，能否把怪物的血量恰好打到0并且攻击次数最少。

T2-挑战怪物

题目描述:

使用若干次物理攻击和至多一次魔法攻击，能否把怪物的血量恰好打到0并且攻击次数最少。

贪心+数论，若怪物剩余血量为质数，则用魔法攻击并结束挑战。否则用物理攻击让怪物血量不断减少，怪物剩余血量为0，结束挑战，如果怪物剩余血量变负数了都不曾出现质数，则不能击败怪物。

#include

using namespace std;

int t, h;

bool f(int x) { //判断x是否为质数

if(x == 1) return false;

for(int i = 2; i * i

if (x % i == 0) return false;

}

return true;

}

int main {

cin >> t;

while(t--) {

cin >> h;

int w = 1; //物理攻击伤害

for(int i = 1; h > 0; i++) {

if(f(h) == true) { //若血量为质数，魔法攻击，击败怪物

cout

break;

}

h -= w; //物理攻击

if (h == 0) { //怪物被物理攻击打死了

cout

break;

}

w *= 2; //下次伤害加倍

}

if(h

cout

}

}

return 0;

}

来源：星空教育