思路

我们对敌人按照血量进行由小到大排序。我们思考一下对于A子弹和B子弹的比较，发现只有在面对敌人的最少血量为1的时候，A子弹才会比B子弹优势。所以我们用贪心策略。一旦遇到敌人血量为1，就用A子弹，一旦没有血量为1的敌人的时候，我们其他敌人都用B子弹。

代码

C++代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int arr[MAXN];
int main(){
	int t, n;
	cin >> t >> n;
	while(t--){
		for(int i = 1; i <= n; i++){
			cin >> arr[i];
		}
		int ans = 0;
		sort(arr + 1, arr + 1 + n);//排序
		int i = 1;
		while(i <= n){
			if(arr[i] >= 2)break;//遇到血量大于等于2，后续全用B子弹打
			else if(arr[i] == 1){//遇到血量为1的敌人时，用A子弹打
				ans++;
				arr[i + 1]--;//A子弹有2发，所有后面一发打后面的敌人
			}
			i++;
		}
		if(i <= n)ans += n - i + 1;
		cout << ans << endl;
	}
}
// 3 3
// 1 2 1
// 2 3 2
// 1 2 3

JAVA代码

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

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        int n = in.nextInt();
        while(t-- > 0){
            int[] a = new int[n];
            for(int i = 0; i < n; i++)a[i] = in.nextInt();
            Arrays.sort(a);//排序
            int L = 0;
            int res = 0;
            while(L < n){
                if(a[L] >= 2)break;//遇到血量大于等于2，后续全用B子弹打
                else if(a[L] == 1){//遇到血量为1的敌人时，用A子弹打
                    res++;
                    if(L + 1 < n){
                        a[L + 1]--;//A子弹有2发，所有后面一发打后面的敌人
                    }
                }
                L++;
            }
            System.out.println(res + n - L);
        }
    }
}

题目内容

小红是一个游戏迷，最近沉迷于一款飞机大战游戏中。在这个游戏中，他需要控制一架飞机发射子弹，来消灭出现在屏幕中的敌人。为了让游戏更加有趣和挑战性，游戏设置了两种不同的发射按键，每个按键都有不同的特殊效果。

在游戏中，按下 $A$ 键，飞机会发射出 $2$ 枚子弹，每个子弹会对命中的敌人造成 $1$ 点固定伤害，但不能作用于同一个敌人。而按下 $B$ 键，飞机会发射出 $1$ 枚子弹，该子弹能够对命中的敌人造成巨额伤害并瞬间将其秒杀。

整个游戏一共有 $T$ 个关卡，每个关卡会在屏幕中同时出现 $N$ 个敌人，这 $N$ 个敌人所能承受的伤害也已经确定。当小红消灭当前关卡的所有敌人后，发射出去多余的子弹会消失，游戏会自动进入下一个关卡。

作为一名游戏高手，小红总是能够操纵子弹命中想要攻击的敌人。但是，他还是很好奇每个关卡自己最少需要按几次发射按键才能将所有敌人全部消灭。他找到了你，希望你能够帮助他解决这个问题。

输入描述

第一行输入一个固定数字 $T$ （ $1\le T \le 1000$ ）表示关卡的总数量， $N$ （ $1\le N\le 200$ ）表示每个关卡出现的敌人数量。

接下来 $T$ 行，每行有 $N$ 个数字 $D_1，D_2，.....,D_N$ （ $1\le D_i \le 200$ ）分别表示这 $N$ 个敌人所能承受的伤害。

输出描述

结果共有 $N$ 行，每行一个数字，分别表示对于这个关卡，最少按几次发射按键就可以将敌人全部消灭。

样例

输入

3 3
1 2 1
2 3 2
1 2 3

输出

2
3
3

样例解释

游戏共有 $3$ 个关卡，每个关卡会出现 $3$ 个敌人。

第一个关卡，先按下 $A$ 键控制子弹消灭第 $1$ 个和第 $3$ 个敌人后，再按下 $B$ 键消灭第二个敌人。所以最少按 $2$ 次。

第二个关卡，按下 $3$ 次 $B$ 键分别消灭这 $3$ 个敌人。

第三个关卡，按下 $3$ 次 $B$ 键分别消灭这 $3$ 个敌人。也可以按 $3$ 次 $A$ 键，敌人剩余承受伤害的变化为： [1, 2, 3] ->[1，1，2]->[1,0,1]->[0，0，0]