米哈游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;
}