Monocarp正在玩电脑游戏。在这款游戏中,他的角色与不同的怪物战斗。
角色和怪物之间的战斗是这样的。假设角色最初有生命值hC和攻击dC;怪物最初拥有生命值hM和攻击dM。战斗包括以下几个步骤:
角色攻击怪物,怪物的生命值减少dC;
怪物攻击角色,通过dM降低角色的生命值;
角色攻击怪物,怪物的生命值减少dC;
怪物攻击角色,通过dM降低角色的生命值;
以此类推,直到战斗结束。
当某人的健康状况变得不积极时,争吵就结束了。0或更少)。如果怪物的命值变得非积极,那么角色就会获胜,否则怪物就会获胜。
Monocarp的角色目前的生命值等于hC,攻击值等于dC。他想杀死一个生命值等于hM,攻击值等于dM的怪物。在战斗前,Monocarp可以花费最多k个金币来升级角色的武器和/或护甲;每次升级只需要花费1个硬币,每次武器升级增加角色的攻击力w,每次盔甲升级增加角色的生命值a。
如果Monocarp在升级上花费金币,Monocarp的角色能杀死怪物吗?
输入
第一行1个整数t(1≤t≤5⋅104),为测试用例个数;每个测试用例由三行组成:
第一行包含两个整数hC和dC(1≤hC≤1015;1≤dC≤109)-角色的生命值和攻击;
第二行包含两个整数hM和dM(1≤hM≤1015;1≤dM≤109)-怪物的生命值和攻击;
第3行为3个整数k、w、a(0≤k≤2⋅105;0≤w≤104;0≤a≤1010)- Monocarp可以花费的最大硬币数,每次武器升级增加到角色攻击的数量,以及每次盔甲升级增加到角色生命值的数量。
所有测试用例的k之和不超过2⋅105。
输出
对于每个测试用例,如果能够通过优化选择升级而杀死怪物,则输出YES。否则,打印NO。
样例
输入样例1
4
25 4
9 20
1 1 10
25 4
12 20
1 1 10
100 1
45 2
0 4 10
9 2
69 2
4 2 7
输出样例1
YES
NO
YES
YES
分析
将 i 从 0 到 k 依次枚举花费 i 枚金币升级武器( k-i 枚升级防御)时能否杀死怪兽(攻击次数*攻击力>=怪物的血量)
问题有两个:一是当角色血量不能被怪物攻击力整除时,要加一向上取整(ceil函数是什么鬼);二是血量和攻击力都超出了int,应该用long long(包括攻击次数,最后忘记修改这里导致wrong answer)
代码
#include <cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main(){
long long i,j,k,t;//这里用long long
scanf("%d",&t);
while(t--){
long long hc,dc,hm,dm,k,u,a;//这里用long long
scanf("%lld %lld %lld %lld %lld %lld %lld",&hc,&dc,&hm,&dm,&k,&u,&a);
int flag=1;
for(i=0;i<=k;i++){
int cs;
if((hc+(i*a))%dm){//我的向上取整的思路:能整除就直接将取模作为攻击次数,不能整除就加一
cs=((hc+(i*a))/dm)+1;
}
else{
cs=((hc+(i*a))/dm);
}
long long gj=dc+((k-i)*u);//这里也要用long long,交之前没发现寄了
if((cs*gj)>=hm){
printf("YES\n");
flag=0;
break;
}
}
if(flag){
printf("NO\n");
}
}
return 0;
}
反思
一开始没有意识到要向上取整,导致wa在第二个点
修改后没有发现变量超过了int的范围,导致一直wa在第五个点
最后忘记改次数变量 cs 的类型(原来是int,应该改为long long),导致没交上ac答案
所以以后修改变量类型的时候应当考虑到所有相关的变量的类型,如果内存空间允许的话还是全部换成和被修改的变量一样的类型保险
原文地址:http://www.cnblogs.com/Chitoge/p/16851701.html