题目名称 4053. [CSP 2024 S]决斗
输入输出 duel.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试数据 20
题目来源 Gravatarsyzhaoss 于2024-10-27加入
开放分组 全部用户
提交状态
分类标签
NOIP/CSP 贪心
分享题解
通过:11, 提交:30, 通过率:36.67%
GravatarAeeE5x 100 0.210 s 3.44 MiB C++
Gravatarxxz 100 0.230 s 3.94 MiB C++
Gravatar喵喵喵 100 0.234 s 3.64 MiB C++
Gravatar梦那边的美好ET 100 0.262 s 3.78 MiB C++
Gravatar1nclude 100 0.262 s 3.98 MiB C++
Gravatardustsans 100 0.270 s 3.77 MiB C++
Gravatarpcx 100 0.407 s 3.42 MiB C++
Gravatar 100 0.426 s 3.70 MiB C++
Gravatarwxs 100 0.435 s 3.64 MiB C++
GravatarLixj 100 0.471 s 3.70 MiB C++
关于 决斗 的近10条评论(全部评论)

4053. [CSP 2024 S]决斗

★   输入文件:duel.in   输出文件:duel.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目描述】

今天是小 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

【样例1说明】

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

【样例1输入】

10
136 136 136 2417 136 136 2417 136 136 136

【样例1输出】

8

【样例3/4】

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

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

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

样例下载

【数据规模与约定】

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

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