方法思路

这道题需要确定最少的攻击次数来消灭所有怪物，考虑到怪物死亡时会自爆并对其他怪物造成等同于初始血量的伤害，我们可以采用贪心策略：

1. 按血量从小到大排序怪物
2. 优先攻击血量较小的怪物，利用它们的自爆伤害来减少总攻击次数
3. 维护当前怪物的实际血量，考虑之前怪物自爆造成的伤害

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        String[] input = br.readLine().split(" ");
        int[] monsters = new int[n];
        for (int i = 0; i < n; i++) {
            monsters[i] = Integer.parseInt(input[i]);
        }
        
        // 按血量排序
        Arrays.sort(monsters);
        
        long totalAttacks = 0;
        long explodeDamage = 0;
        
        for (int i = 0; i < n; i++) {
            // 计算当前怪物需要的攻击次数
            long neededAttacks = Math.max(0, monsters[i] - explodeDamage);
            totalAttacks += neededAttacks;
            
            // 怪物死亡后自爆，增加伤害
            explodeDamage += monsters[i];
        }
        
        System.out.println(totalAttacks);
    }
}

Python

def min_attacks():
    n = int(input())
    monsters = list(map(int, input().split()))
    
    # 按血量排序
    monsters.sort()
    
    total_attacks = 0
    explode_damage = 0
    
    for monster in monsters:
        # 计算当前怪物需要的攻击次数
        needed_attacks = max(0, monster - explode_damage)
        total_attacks += needed_attacks
        
        # 怪物死亡后自爆，增加伤害
        explode_damage += monster
    
    return total_attacks

print(min_attacks())

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> monsters(n);
    for (int i = 0; i < n; i++) {
        cin >> monsters[i];
    }
    
    // 按血量排序
    sort(monsters.begin(), monsters.end());
    
    long long totalAttacks = 0;
    long long explodeDamage = 0;
    
    for (int i = 0; i < n; i++) {
        // 计算当前怪物需要的攻击次数
        long long neededAttacks = max(0LL, (long long)monsters[i] - explodeDamage);
        totalAttacks += neededAttacks;
        
        // 怪物死亡后自爆，增加伤害
        explodeDamage += monsters[i];
    }
    
    cout << totalAttacks << endl;
    return 0;
}