思路:贪心

$\qquad$这题需要考虑的细节有点多。

$\qquad$假设数组nums,首先需要证明的是，对于排序后的数组，元素nums[i]（不考虑最后一个元素）如何在更小的AOE释放次数下删除。如果nums[i]能够被k次E技能删除，那么nums[i-1]一定也可以，相应的之前的一定都可以。由于题目指定了R一定大于0，那么如果释放更多次R范围伤害，也能减少E技能的使用。

所以贪心的思路如下：

$\quad$（1）首先将数组进行排序，从前往后遍历数组，将尽可能靠前的较小元素削减到50%及一下（这种削弱对后面的更大元素也同时造成），用两个变量cntE和cntR统计两个技能的使用次数。

$\quad$（2）这里暂时不需要考虑中途把某个元素爆成0的情况，从样例也可以看出，就算中途哪个元素被抬走了，它也会贡献一个R技能

$\quad$（3）现在考虑最后一个怪物扛不住cntR次爆的情况，由于遍历是从前往后的，手动E技能触发的次数已经固定，可以证明的是，对于升序数组，如果最后一个元素扛不住cntR次爆，那么倒数第二个元素一定也不可以，相应的更靠前的元素也不行，所以需要在遍历结束后，特判最后一个元素在生前最多可以经历的R爆的次数。

$\quad$（4）同理，如果最后一个元素扛住了所有伤害，那么只能使用手动E技能进行抹除。

时间复杂度

排序:$O(nlogn)$

代码

C++

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
void solve()
{
	int n;
	cin >> n;
	vector<ll>nums(n);
	for (int i = 0; i < n; i++)
		cin >> nums[i];
	ll E, R;
	cin >> E >> R;
	int cntE = 0, cntR = 0;
	sort(nums.begin(), nums.end());	   // 排序
	for (int i = 0; i < n; i++)
	{
		ll cur = nums[i] - E * cntE - R * cntR;
		if (cur + cur <= nums[i])	// 当前已经小于等于50%，直接爆
			++cntR;
		else	// 手动削减到50%及一下，然后爆
		{
			ll tmp = cur - (nums[i] >> 1);
			cntE += (tmp + E - 1) / E;
			++cntR;
		}
	}
	// 特判最后一个
	ll lst = nums[n - 1] - E * cntE;
	if (lst - R * cntR > 0)	 // 只需要杀最后一个
		cntE += (lst - R * cntR + E - 1) / E;
	else   // 最后一个中途死了
	{
		ll nR = (lst + R - 1) / R;
		cntR = min(cntR, nR);
	}
	cout << cntE << " " << cntR << endl;
}
int main()
{
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}

java

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            // t组数据
            int t = (int) in.nval;
            in.nextToken();
            for (int k = 0; k < t; k++) {
                // 怪物数量
                int n = (int) in.nval;
                in.nextToken();
                // 怪物总hp
                int[] hp = new int[n];
                // 怪物剩余hp
                int[] surplusHp = new int[n];
                // 怪物是否触发过被动技能
                boolean[] trigger = new boolean[n];
                for (int i = 0; i < n; i++) {
                    hp[i] = ((int) in.nval);
                    surplusHp[i] = hp[i];
                    in.nextToken();
                }
                // e技能伤害
                int e = ((int) in.nval);
                in.nextToken();
                // 被动伤害
                int r = ((int) in.nval);
                in.nextToken();

                int eCnt = 0;
                int rCnt = 0;
                while (!isDone(surplusHp)) {
                    // 使用E技能
                    doEskill(hp, surplusHp, e);
                    eCnt++;
                    // 判断触发几次转圈圈
                    int times = getTriggerTimes(hp, surplusHp, trigger);
                    while (!isDone(surplusHp) && times > 0) {
                        // 执行r技能
                        doRskill(hp, surplusHp, r);
                        times--;
                        rCnt++;
                        // 判断触发几次转圈圈
                        times += getTriggerTimes(hp, surplusHp, trigger);
                    }
                }
                out.println(eCnt + " " + rCnt);
                out.flush();
            }

        }
    }

    // 使用E技能
    public static void doEskill(int[] hp, int[] surplusHp, int e) {
        for (int i = 0; i < surplusHp.length; i++) {
            surplusHp[i] -= e;
            if (surplusHp[i] < 0) surplusHp[i] = 0;
        }
    }

    // 判断触发几次转圈圈
    public static int getTriggerTimes(int[] hp, int[] surplusHp, boolean[] trigger) {
        int cnt = 0;
        for (int i = 0; i < hp.length; i++) {
            if (!trigger[i] && surplusHp[i] <= hp[i] / 2) {
                trigger[i] = true;
                cnt++;
            }
        }
        return cnt;
    }

    // 使用转圈圈
    public static void doRskill(int[] hp, int[] surplusHp, int r) {
        for (int i = 0; i < surplusHp.length; i++) {
            surplusHp[i] -= r;
            if (surplusHp[i] < 0) surplusHp[i] = 0;
        }
    }

    // 判断怪兽是否全部死掉
    // true: 全部死掉
    public static boolean isDone(int[] surplusHp) {
        for (int hp : surplusHp) {
            if (hp > 0) {
                return false;
            }
        }
        return true;
    }
}

python

import sys
import math
from typing import List


def solve():
    n = int(input())
    nums = list(map(int, input().split()))
    E, R = map(int, input().split())
    def dmg(cntE, cntR):
        return cntE * E + cntR * R
    def end():
        return nums[-1] <= dmg(cntE, cntR)
    nums.sort()
    cntE, cntR = 0, 0
    t = nums[-1] // E
    for i in range(0, n):
        cntE += math.ceil((nums[i] / 2 - dmg(cntE, cntR)) / E)
        if end():
            return cntE, cntR
        cntR = i + 1
        if end():
            return cntE, cntR5
        j = i + 1
        while j < n and nums[j] / 2 <= dmg(cntE, cntR):
            j += 1
            cntR += 1
            if end():
                return cntE, cntR        
        i = j
    return cntE + math.ceil((nums[-1] - dmg(cntE, cntR)) / E), cntR

T = int(input())
for _ in range(T):
    print(' '.join(map(str, solve())))

题目描述

米小游喜欢肝模拟宇宙，而且特别喜欢用黑塔单通（坐牢）模拟宇宙

有一天，他遇到了$n$个怪物，第$i$个怪物的生命值为$h_i$。 由于被守护者之影禁用了普通攻击，黑塔现在只能使用E技能攻击敌人。具体地说，黑塔每次使用E技能，会对敌方全体造成E点伤害。 除此之外，每当一个怪物的生命值首次减小到其最大生命值的50%及以下(含50%)时，如果敌方尚有怪物存活(生命值大于零)，那么黑塔就会自动释放一次追加攻击“转圈圈”，对敌方全体造成R点伤害。如果一次攻击同时使多个敌人满足以上条件，那么黑塔也会连续释放多次“转圈圈”，直到“转圈圈”次数耗尽或者敌人全部倒下为止。在“转圈圈”结束之前，黑塔无法再次使用E技能。 作为天才俱乐部#83的天才，黑塔只用了0.0114514秒就算出了自己需要使用多少次E技能才能击败这些怪物，以及在这个过程中她会释放多少次“转圈圈”。她觉得这个问题太简单了，于是将其留给了你作为课后习题。

输入描述

第一行一个正整数T，表示有T组数据, 对于每一组数据，第一行一个正整数$n$，表示怪物的数量 第二行$n$个正整数$h_1,h_2……h_n$,表示每个怪物的生命值; 第三行两个正整数E，R，分别表示黑塔E技能的伤害和“转圈圈”的伤害

$1\le n\le 10^5$,$1\le T\le 10$,$1\le h_i,E,R\le 10^9$

输出描述

对于每一组数据，输出一行两个正整数$cntE, cntR$,分别表示黑塔使用E技能的次数和“转圈圈”的次数。

样例输入

3
5
100 50 60 80 70
25 10
5
100 50 60 80 70
20 20
5
100 200 300 4000 5000
50 1000

样例输出

2 5
2 3
1 5

提示

对于第一组数据:
初始怪物生命值为[100,50,60,80,70];
黑塔使用E技能，怪物生命值变为[75,25,35,55,45];
怪物2生命值小于等于50%，触发一次转圈圈，怪物生命值变为[65,15,25,45,35]怪物3,5生命值小于等于50%，触发两次转圈圈，生命值变为[45,0,5,25,15];
怪物1,4触发两次转圈圈，生命值变为[25,0,0,5,0]
使用E技能，生命值变为[0,0,0,0,0]，战斗结束；一共使用2次E，5次转圈圈:

对于第二组数据:
初始怪物生命值为[100,50,60,80,701;
黑塔使用E技能，怪物生命值变为[80,30,40,60,50];
再次使用E,生命值变为[60,10,20,40,30];
怪物2,3,4,5触发四次转圈圈，但是只转3次所有怪物就全部被击杀，因此一共使用2次E，3次转圈圈。

对于第三组数据:
初始生命值为[100,200,300,4000,5000]
使用E技能，[50,150,250,3950,49501
怪物1触发一次转圈圈，[0,0,0,2950,3950]
怪物2，3触发两次转圈圈，[0,0,0,950,1950]
怪物4，5触发两次转圈圈，[0,0,0,0,0]，战斗结束，一共使用1次E，5次转圈圈。