主页 / 问题 / 1551883
Accepted
Curtisol
Asked:2023-11-18 04:00:02 +0000 UTC2023-11-18 04:00:02 +0000 UTC

奥林匹克任务-最优选择

  • 772

请帮我解决问题。在我看来，这项任务很艰巨。说实话，我不知道如何解决。虽然有一个想法可以简单地遍历所有战士的组合，但是数量太多了，所以我必须寻求帮助）给我一个解决方案的想法））

问题

你是贝尔兰繁荣首都的快乐市长，但运气不好 - 一个可怕的怪物定居在郊区，并正在攻击在首都和邻近城市之间行驶的贸易商队。为了摆脱怪物，你决定从城市的冒险家公会雇佣一支英雄团队。公会提供 n 个战士，第 i 个战士拥有高生命值单位和低攻击单位。需要杀死的怪物有一定的生命值。

只要怪物还剩下正数的生命值，并且至少一名英雄还剩下正数的生命值，就会发生以下情况：

首先，每个活着的英雄都会对怪物造成相当于其攻击值的伤害。如果怪物的生命值降到零，则战斗结束；然后，如果怪物还活着，它会对每个英雄造成 1 点伤害。每个生命值降至零的英雄都会死亡。由于金库有限，你需要雇佣最少数量的英雄来杀死怪物。但你也不希望队伍中至少有一名英雄死亡，所以你需要招募最少数量的英雄，这样他们才能不损失地击杀怪物。

笔记

在第一组输入数据中，三个英雄就足以无损失地击杀怪物。例如，这些英雄可能是数字2、3、4。他们的总攻击力是6，并且两次攻击就能杀死怪物。

在第一次测试的第二组输入数据中，有一个英雄，他的实力足以立即杀死怪物。

输入格式

输入数据的第一行包含一个整数 t (1 ≤ t ≤ 1000) — 输入数据集的数量。以下是各组的说明。每组的第一行包含整数 a (1 ≤ a ≤ 109) — 怪物的生命值。每组的第二行包含一个整数 n (1 ≤ n ≤ 2⋅105) — 公会提供雇佣的战士总数。每组的第三行包含 n 个整数 h1,h2,…,hn (1 ≤ hi ≤ 109) — 每个英雄的生命值单位。每组第四行包含n个整数d1,d2,…,dn (1 ≤ di ≤ 109)——每个英雄的攻击单位。保证所有输入数据集的n之和不超过2⋅105

输出格式

对于每组输入，在单独的行上打印一个整数：必须雇佣才能无损失地杀死怪物的英雄的最小数量，如果这是不可能的，则为 -1。

例子

Входные данные: 
2
12
5
1 2 3 3 4
2 4 1 1 1
10
1
1
14
Выходные данные:
3
1

哦对了，时间限制是2秒。由于您需要显示所需的战士数量，而不是他们的索引，因此您可能不需要查看所有选项或类似的内容

以@StanislavVolodarskiy的想法为基础，我用python写了这个：

answer = list()
for _ in range(int(input())):
    a = int(input())
    n = int(input())
    hp_war = list(map(int, input().split()))
    d_war = list(map(int, input().split()))
    attack = dict()
    for i in range(n):
        attack[d_war[i]] = attack.get(d_war[i], list()) + [hp_war[i]]
    attack = {key: sorted(attack[key], reverse=True) for key in sorted(attack, reverse=True)}

    max_h_lvl, k = max(hp_war) + 1, n + 1
    h_left, h_level, h_right = 1, max_h_lvl // 2, max_h_lvl
    while True:
        sum_attack, flag, cnt = 0, 0, 0
        for a_w in attack:
            for h_w in attack[a_w]:
                if h_w >= h_level:
                    cnt += 1
                    sum_attack += a_w
                    if sum_attack * h_level >= a:
                        flag = 1
                        break
                    continue
                break
            if flag == 1:
                break
        if flag:
            k = min(k, cnt)
        if h_right - h_left <= 1:
            break
        if flag:
            h_right, h_level = h_level, (h_level + h_left) // 2
        else:
            h_left, h_level = h_level, (h_level + h_right) // 2

    if k == n + 1:
        answer.append(-1)
    else:
        answer.append(k)

for ans in answer:
    print(ans)

在我看来，这是一个有效的解决方案，但在测试系统看来却不是。尽管如此，我还是错过了一些东西。但什么？

олимпиада

2 个回答

  1. Best Answer

    groups- 将健康状况与具有该健康状况的英雄索引列表相匹配的字典。字典的处理是为了增加健康。h- 目前的健康水平。

    heroes- 英雄列表，按伤害降序排列。k将英雄列表变成一个堆栈。来自其他国家的英雄参加战斗heroes[:k]，但仅限于生命值≥的人h。

    count- 战斗中英雄的数量，damage- 他们每步的总伤害。

    该循环由四个步骤组成：

    1. 在循环开始时我们有一个命令。虽然它的总伤害足以逐步击败怪物h，但我们还是一一消灭了英雄。count并作相应调整damage。

    2. 现在我们的球队还不足以赢得胜利。我们添加英雄，直到有足够的英雄。

    3. 如果有足够多的英雄可以获胜，我们会向上级报告每轮获胜的英雄数量h。否则我们什么也不做。

    4. 我们正在为下一轮做准备 - 我们从当前健康组中删除了所有英雄。接下来的战斗不需要它们——生命值不够。

    第 1 点和第 2 点似乎做了额外的工作。这是事实，但这样的情况并不多。如果命令最初很小，则第一个循环将执行零次。如果命令最初足够或太大，那么第二个循环将执行一次。

    排序复杂度为NlogN ，健康周期复杂度为N。

    def counts(a, heroes):
    groups = {}
    for i, (_, h) in enumerate(heroes):
        groups.setdefault(h, []).append(i)

    k = 0
    count = 0
    damage = 0
    for h, indices in sorted(groups.items()):
        while k > 0 and damage * h >= a:
            k -= 1
            if heroes[k][1] >= h:
                count -= 1
                damage -= heroes[k][0]
        while k < len(heroes) and damage * h < a:
            if heroes[k][1] >= h:
                count += 1
                damage += heroes[k][0]
            k += 1
        if damage * h >= a:
            yield count
        for i in indices:
            if i < k:
                count -= 1
                damage -= heroes[i][0]


def solve(a, h, d):
    return min(counts(a, sorted(zip(d, h), reverse=True)), default=-1)


def main():
    t = int(input())
    for _ in range(t):
        a = int(input())
        input() # skip n
        h = tuple(map(int, input().split()))
        d = tuple(map(int, input().split()))
        print(solve(a, h, d))


main()
    • 1

  2. 按健康状况降序排列。我们计算具有相同健康状况的群体所累积的数量，乘以最低健康状况，从最健康的开始。一旦超出暴民的生命值 - 停止。将剩余的按强度降序排列。我们开始一次从最弱的人中剔除一个。我们如何不杀人——前一个选择就是解决方案。

    • 0

相关问题