核心内容摘要
邻家女孩的秘密：藏在寻常日子里的微光与蜕变
2024信奥赛C提高组csp-s复赛真题及题解决斗题目描述今天是小 Q 的生日他得到了n nn张卡牌作为礼物。
这些卡牌属于火爆的“决斗怪兽”其中第i ii张卡代表一只攻击力为r i r_iri防御力也为r i r_iri的怪兽。
一场游戏分为若干回合。
每回合小 Q 会选择某只怪兽i ii以及另一只怪兽j ( i ≠ j ) j(i \neq j)j(ij)并让怪兽i ii向怪兽j jj发起攻击。
此时若怪兽i ii的攻击力小于等于怪兽j jj的防御力则无事发生否则怪兽j jj的防御被打破怪兽j jj退出游戏不再参与到剩下的游戏中。
一只怪兽在整场游戏中至多只能发起一次攻击。
当未退出游戏的怪兽都已发起过攻击时游戏结束。
小 Q 希望决定一组攻击顺序使得在游戏结束时未退出游戏的怪兽数量尽可能少。
输入格式输入的第一行包含一个正整数n nn表示卡牌的个数。
输入的第二行包含n nn个正整数其中第i ii个正整数表示第i ii个怪兽的攻击力及防御力r i r_iri。
输出格式输出一行包含一个整数表示游戏结束时未退出游戏的怪兽数量的最小值。
输入输出样例 1输入 15 1 2 3 1 2输出 12输入输出样例 2输入 210 136 136 136 2417 136 136 2417 136 136 136输出 28说明/提示【样例 1 解释】其中一种最优方案为第一回合让第2 22只怪兽向第1 11只怪兽发起攻击第二回合让第5 55只怪兽向第4 44只怪兽发起攻击第三回合让第3 33只怪兽向第5 55只怪兽发起攻击。
此时没有退出游戏的怪兽都进行过攻击游戏结束。
可以证明没有更优的攻击顺序。
【数据范围】对于所有测试数据保证1 ≤ n ≤ 10 5 1 \leq n \leq 10^51≤n≤1051 ≤ r i ≤ 10 5 1 \leq r_i \leq 10^51≤ri≤105。
测试点n nnr i r_iri特殊性质1 ∼ 4 1\sim 41∼4≤ 10 \leq 10≤10≤ 10 5 \leq 10^5≤105无特殊性质5 ∼ 10 5\sim 105∼10≤ 10 5 \leq 10^5≤105≤ 2 \leq 2≤2^11 ∼ 15 11\sim 1511∼15≤ 30 \leq 30≤30≤ 10 5 \leq 10^5≤105特殊性质 A16 ∼ 20 16\sim 2016∼20≤ 10 5 \leq 10^5≤105^无特殊性质特殊性质 A保证每个r i r_iri在可能的值域中独立均匀随机生成。
思路分析题目要求通过安排怪兽的攻击顺序使得游戏结束时未退出游戏的怪兽数量尽可能少。
经过分析可以得出一个关键结论最终存活的怪兽数量恰好等于所有攻击力中出现次数的最大值。
这是因为在最优策略下只有出现次数最多的那些攻击力的怪兽能够存活其余攻击力的怪兽都可以被淘汰。
算法思路统计每个攻击力值出现的次数。
找出出现次数的最大值。
该最大值即为最终存活怪兽的最小数量。
时间复杂度读取输入和统计出现次数O(n)查找最大值O(max(r i r_iri))其中r i ≤ 10 5 r_i ≤ 10^5ri≤105总体复杂度为 O(n max(r i r_iri))在给定数据范围内完全可行。
代码实现#includebits/stdc.husingnamespacestd;constintMAXR100010;// r_i 的最大值intcnt[MAXR];// 统计每个攻击力出现的次数数组下标对应攻击力值intmain(){intn;// 怪兽数量cinn;intmaxCnt0;// 记录出现次数的最大值for(inti0;in;i){intr;cinr;cnt[r];// 攻击力为 r 的怪兽数量加1maxCntmax(maxCnt,cnt[r]);// 更新最大值}// 输出结果最终存活怪兽的最小数量等于最大出现次数coutmaxCntendl;return0;}功能分析输入处理读取怪兽数量 n 和每个怪兽的攻击力 r_i。
统计频率使用数组cnt记录每个攻击力值出现的次数。
求最大值在统计过程中实时更新出现次数的最大值。
输出结果最大值即为最终存活怪兽的最小数量。
算法证明贪心策略从大到小处理攻击力值每次尽可能用当前可用的攻击次数淘汰当前攻击力的怪兽。
可用的攻击次数始终是历史出现次数的最大值。
最终存活数量等于最终可用的攻击次数即所有攻击力中出现次数的最大值。
因此直接输出最大出现次数即可得到最优解。
各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}