米哈游B题 8.06
昨天笔的时候没做完,回去想了下整体的逻辑记录一下
首先先证明要从血量最大的怪物开始砍:
假设我们有n个怪物,怪物的总血量是不变的,我们砍一刀造成的伤害要么是1, 要么是k,k是砍到半血后爆炸对场上存活的所有怪物造成的伤害,如果我们想少砍,那么就需要k尽量大,如果我们从小的砍起,假设第l1个怪物在我们砍l2的怪物时死亡,那么我们在砍l2后面的怪物时,l1及其之前的怪物都吃不到伤害,相当于减小了k,相反,如果我们从大的开始砍,那么大的当我们砍到l1时,其后面的元素一定比他先死,并且死了产生的伤害一定还会影响到l1之前的元素,这样就可以尽可能多的增加k值。这样说可能有点抽象,但想一个具体的例子,3个怪物,2,5,10的生命值,如果我们先把2砍死,当我们让5,10产生aoe时,这个aoe每次只能产生2点伤害,但我们先砍10,aoe能产生3点伤害,并且2死掉后产生的aoe还是会作用于10。
下面贴具体的代码,先遍历一次,每次先判断怪物i前面有多少个怪物,在判断其后面有多少个怪物爆炸了,如果爆炸伤害可以让这个怪物掉到半血,那我们就不用砍了,否则砍到半血,记录times。这步完成后,会有一些爆炸没有记录上,比如对于第一个元素,2到n-1的爆炸对他还没应用上,再把这一部分血量扣除。
最后还活着的直接用times加上血量,代码如下,有不对的地方请指正:
#include<bits/stdc++.h> using namespace std; int main(){ //input int m_number; cin >> m_number; vector<int> health; for(int i = 0; i < m_number; i++){ int temp; cin >> temp; health.push_back(temp); } //排序 sort(health.begin(), health.end()); reverse(health.begin(), health.end()); //记录初始数据 vector<int> health_init; for(int i = 0; i < health.size(); i++){ health_init.push_back(health[i]); } //记录遍历到i的时候,i后面有多少元素爆了 vector<int> b_hurt(m_number, health.size()); for(int i = 0; i < health.size(); i++){ for(int j = health.size() - 1; j >= 0; j--){ if(i >= j){ b_hurt[i] = i + 1; break; } if((health[j] - i) <= health[j] / 2 && i < j) b_hurt[i] = j; else break; } } int times = 0; int m_hurt = 0;//i前面的元素爆炸产生的最高伤害; for(int i = 0; i < health.size(); i++){ health[i] -= m_hurt; // 前面的爆炸产生的伤害 health[i] -= (m_number - b_hurt[i]); //后面的爆炸产生的伤害 if(health[i] <= health_init[i] / 2){ //判断是否爆炸 m_hurt++; health[i]--; continue; } //没爆炸的话 times += (health[i] - health_init[i] / 2);//砍这么多次让他爆炸 health[i] = health_init[i] / 2 - 1; //记录爆炸后的血量 m_hurt++; } //判断第二波爆炸造成的伤害 for(int i = 0; i < health.size(); i++){ if(health[i] <= 0) continue; health[i] -= (b_hurt[i] - i - 1); } //剩下没死的砍死即可 for(int i = 0; i < health.size(); i++){ if(health[i] > 0) times += health[i]; } cout << times << endl; return 0; }#米哈游##游戏客户端开发#