【题解】Gamer Hemose

题目描述

One day, Ahmed_Hossam went to Hemose and said "Let's solve a gym contest!". Hemose didn't want to do that, as he was playing Valorant, so he came up with a problem and told it to Ahmed to distract him. Sadly, Ahmed can't solve it... Could you help him?

There is an Agent in Valorant, and he has n weapons. The ii -th weapon has a damage value a_i

, and the Agent will face an enemy whose health value is H .

The Agent will perform one or more moves until the enemy dies.

In one move, he will choose a weapon and decrease the enemy's health by its damage value. The enemy will die when his health will become less than or equal to 0 . However, not everything is so easy: the Agent can't choose the same weapon for 2 times in a row.

What is the minimum number of times that the Agent will need to use the weapons to kill the enemy?

输入格式

Each test contains multiple test cases. The first line contains the number of test cases t (1\le t\le 10^5). Description of the test cases follows.

The first line of each test case contains two integers n and H (2\le n\le 10^3,1\le H\le 10^9) — the number of available weapons and the initial health value of the enemy.

The second line of each test case contains n integers a_1,a_2,\dots,a_n (1\le a_i\le 10^9) — the damage values of the weapons.

It's guaranteed that the sum of n over all test cases doesn't exceed 2\cdot 10^5.

输出格式

For each test case, print a single integer — the minimum number of times that the Agent will have to use the weapons to kill the enemy.

输入输出样例

输入 #1

3
2 4
3 7
2 6
4 2
3 11
2 1 7

输出 #1

1
2
3

分析

显然，最优方案一定是交替使用伤害值最大的两种武器。所以我们可以对所有武器按伤害值排序，得到最大的两个伤害值 d_1 和 d_2。然后得到可以交替使用两种武器攻击的次数是 h/(d_1+d_2)。接下来依 h-h/(d_1+d_2) 的大小再处理一下最后还需要再进行几次攻击即可。

时间复杂度 O(n \log n)。

代码

#include<bits/stdc++.h>
using namespace std;
int a[1001];
bool cmp(int a,int b){
    return a>b;
}
int t,n,h;
int main() {
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&h);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+1+n,cmp);
        int sum=a[1]+a[2];
        int ans=(h/sum)*2;
        h-=(ans/2)*sum;
        if(h-a[1]>0){
            ans+=2;
        }else if(h!=0){
            ans+=1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=4tiqlv6p5maq

最后修改：2022 年 08 月 14 日 05 : 16 PM

© 允许规范转载