当前位置:首页 > 贪心 > 正文
CSPS2024决斗(提高组A题)
175+

题目大意:n个怪兽决斗,每个怪兽最多可以攻击一次其他怪兽,被攻击弱的会退出游戏,请问如何安排攻击,才能使未退出游戏的怪兽尽量少?输出最小值。

题目描述

今天是小 Q 的生日,他得到了 $n$ 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”,其中,第 $i$ 张卡代表一只攻击力为 $r_i$,防御力也为 $r_i$ 的怪兽。

一场游戏分为若干回合。每回合,小 Q 会选择某只怪兽 $i$ 以及**另一只**怪兽 $j(i \neq j)$,并让怪兽 $i$ 向怪兽 $j$ 发起攻击。此时,若怪兽 $i$ 的攻击力小于等于怪兽 $j$ 的防御力,则无事发生;否则,怪兽 $j$ 的防御被打破,怪兽 $j$ 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中**至多**只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时,游戏结束。

小 Q 希望决定一组攻击顺序,使得在游戏结束时,未退出游戏的怪兽数量尽可能少。

输入输出格式

输入格式

输入的第一行包含一个正整数 $n$,表示卡牌的个数。

输入的第二行包含 $n$ 个正整数,其中第 $i$ 个正整数表示第 $i$ 个怪兽的攻击力及防御力 $r_i$。

输出格式

输出一行包含一个整数表示游戏结束时未退出游戏的怪兽数量的最小值。

输入输出样例

输入样例 #1

5
1 2 3 1 2

输出样例 #1

2

输入样例 #2

10
136 136 136 2417 136 136 2417 136 136 136

输出样例 #2

8

说明

**【样例 1 解释】**

其中一种最优方案为:第一回合让第 $2$ 只怪兽向第 $1$ 只怪兽发起攻击,第二回合让第 $5$ 只怪兽向第 $4$ 只怪兽发起攻击,第三回合让第 $3$ 只怪兽向第 $5$ 只怪兽发起攻击。此时没有退出游戏的怪兽都进行过攻击,游戏结束。可以证明没有更优的攻击顺序。

**【样例 3】**

见选手目录下的 duel/duel3.in 与 duel/duel3.ans。

该样例满足 $\forall 1 \leq i \leq n, r_i \leq 2$。

**【样例 4】**

见选手目录下的 duel/duel4.in 与 duel/duel4.ans。

**【数据范围】**

对于所有测试数据,保证:$1 \leq n \leq 10^5$,$1 \leq r_i \leq 10^5$。

| 测试点 | $n$ | $r_i$ | 特殊性质 |
| :———-: | :———-: | :———-: | :———-: |
| $1\sim 4$ | $\leq 10$ | $\leq 10^5$ | 无特殊性质 |
| $5\sim 10$ | $\leq 10^5$ | $\leq 2$ | 无特殊性质 |
| $11\sim 15$ | $\leq 30$ | $\leq 10^5$ | 特殊性质 A |
| $16\sim 20$ | $\leq 10^5$ | $\leq 10^5$ | 无特殊性质 |

特殊性质 A:保证每个 $r_i$ 在可能的值域中独立均匀随机生成。

解题思路

贪心:让更多怪兽离开,攻击完其他怪兽再离开。从小打到排序,最小的最容易离开,谁攻击它呢?比他大的最小的,因为越小越难攻击成功,要越先离开。

做法不唯一,从小到大枚举怪兽,指针j遍历不会退找到右边第一个比他大的进行攻击,存在多走一只怪兽,不存在则后续怪兽都不会被击败。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

报歉!评论已关闭.