思路：贪心

给定$n$个怪物，每次攻击能对一个敌人造成1点伤害，当一个敌人血量降到一半及以下时，会对所有敌人都造成一点伤害，求最少需要的攻击次数。

看完题面后，一个很直观的想法是，为了能尽量少的攻击，要将天赋效果尽可能发挥满。也就是说，如果一个敌人能被天赋效果aoe死，我们就不打他了。

而aoe触发次数是固定的n次，所以我们的任务就是决定怪物触发aoe的顺序，以及所有怪触发完aoe后的补刀。

此时我们发现，血量最多的一些怪，即使我们把它们留到最后接受完所有其它怪物触发的aoe，它们本身也不会触发aoe，所以我们可以将它们的aoe优先触发，来得到一些收益，这些怪物的血量阈值就是大于2n，这样它们触发aoe所需的受攻击次数就大于n。

剩余的怪物，先触发血量少的怪物的aoe肯定会优于先触发血量多的情况，因为先触发血量多的可能会把血量少的打死，导致aoe伤害浪费，进而导致总攻击次数增多。

所以我们先将怪物按血量排序，然后计算血量大于2n的怪物的需要手动攻击的攻击次数，同时记录aoe的触发次数$cnt$，再依次从小到大依次处理

当我们判断第$i$个敌人时，如果该敌人被天赋攻击$cnt$次后不能触发天赋，我们就要打到他触发天赋(血量少的要比血量多的先触发天赋，所以这里一定要打)，如果可以触发就省去这一步，之后还要减去后面$n-cnt$个敌人天赋触发扣的血，敌人剩余的血量就是我们额外要攻击的次数，进行累加即可。

时间复杂度$O(NlogN)$

代码

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 输入n
        int[] msters = new int[n];
        for (int i = 0; i < n; i++) {
            msters[i] = scanner.nextInt(); // 输入怪物的血量
        }
        Arrays.sort(msters); // 对怪物血量进行排序
        
        int cnt = 0; // 记录已经触发的aoe次数
        Long ans = 0L; // 记录攻击总次数
        int backId = msters.length - 1;
        while (backId >= 0 && msters[backId] >= 2 * n) {
            ans += msters[backId] - n; // 实际攻击时将接受剩余aoe的血量预留下来
            cnt++; // 触发的aoe次数+1
            backId -= 1; // 移除血量大于等于2n的怪物
        }
        
        for (int i=0;i<backId;i++) {
            int msterhp = msters[i];
            int nowhp = msterhp - cnt; // 当前怪物接受完之前的aoe后的剩余血量
            
            if (nowhp > msterhp / 2) {
                ans += nowhp - msterhp / 2; // 如果当前敌人没有触发aoe，攻击他直到触发他的aoe
                nowhp = msterhp / 2;
            }
            
            if (nowhp - (n - cnt) > 0) {
                ans += nowhp - (n - cnt); // 计算当前敌人需要的额外攻击次数
            }
            
            cnt++; // 触发的aoe次数+1
        }
        
        System.out.println(ans); // 输出攻击总次数
    }
}

python

n = int(input())
msters = list(map(int, input().split()))
msters.sort()
cnt = 0
ans = 0
while msters and msters[-1] >= 2*n:        #先处理血量大于2*n的怪物
    ans += msters.pop() - n            #实际攻击时将接受剩余aoe的血量预留下来，实际攻击次数就相当于接受完n次aoe后的血量
    cnt += 1                    #记录已经触发的aoe次数
for msterhp in msters:        #再依次从小到大取数
    nowhp = msterhp - cnt            #当前怪物接受完之前的aoe后的剩余血量
    if nowhp > msterhp // 2:        #如果当前敌人没有触发aoe，就攻击他直到触发他的aoe
        ans += nowhp - msterhp//2
        nowhp = msterhp//2
    if nowhp - (n-cnt) > 0:    #再计算当前敌人需要的攻击次数
        ans += nowhp - (n-cnt)
    cnt += 1        #记录的aoe次数+1
print(ans)

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
signed main() {
    int n;
    cin >> n; // 输入n
    vector<int> msters;
    for (int i = 0; i < n; i++) {
        int mster;
        cin >> mster; // 输入怪物的血量
        msters.push_back(mster);
    }
    sort(msters.begin(), msters.end()); // 对怪物血量进行排序
    
    int cnt = 0; // 记录已经触发的aoe次数
    long long ans = 0; // 记录攻击总次数
    while (!msters.empty() && msters.back() >= 2 * n) {
        ans += msters.back() - n; // 实际攻击时将接受剩余aoe的血量预留下来
        cnt++; // 触发的aoe次数+1
        msters.pop_back(); // 移除血量大于等于2n的怪物
    }
    
    for (int i = 0; i < msters.size(); i++) {
        int msterhp = msters[i];
        int nowhp = msterhp - cnt; // 当前怪物接受完之前的aoe后的剩余血量
        
        if (nowhp > msterhp / 2) {
            ans += nowhp - msterhp / 2; // 如果当前敌人没有触发aoe，攻击他直到触发他的aoe
            nowhp = msterhp / 2;
        }
        
        if (nowhp - (n - cnt) > 0) {
            ans += nowhp - (n - cnt); // 计算当前敌人需要的额外攻击次数
        }
        
        cnt++; // 触发的aoe次数+1
    }
    
    cout << ans << endl; // 输出攻击总次数
    return 0;
}

题目描述

米小游最近沉迷于一款割草游戏。所谓割草游戏，并不是割草模拟器，而是指一款击杀敌人快，很容易一次性就击杀大量敌人的游戏。

米小游每放一个大范围aoe技能下去，就能看见屏幕上一大片的敌人消失，非常解压。

这天，米小游又在玩这款割草游戏了，他看着面前的$n$个敌人，每个敌人都有$a_{i}$的血，但是突然发现他的技能只能给一个敌人造成$1$点伤害了。但好在米小游所使用的角色点了天赋，开局时给所有敌人添加debuff，当一名敌人血量降到一半及以下时，就会给所有敌人造成$1$点伤害(这个debuff触发一次后消失)。米小游想知道，他最少需要多少次攻击才能击杀所有敌人。

输入描述

第一行输入一个正整数$n$，代表敌人的最大数量

第二行输入$n$个正整数$a_i$，代表每个敌人的血量

$1 \leq n \leq 10^5$

$1 \leq a_i \leq 10^9$

输出描述

一个正整数，代表米小游攻击的最小次数。

样例

输入

2
6 8

输出

10

说明

米小游打第一个敌人3次，触发天赋，每个敌人剩余2，7血。接下来，米小游打第二个敌人3次，触发天赋，每个敌人剩余1，3血。米小游无法再触发天赋了，因此还要攻击4次，总共是10次。

样例2

输入

4
1 2 4 4

输出

1