← 返回目录

算法比赛模拟题精解之“Tairitsu and Dynamic Objects”

第 15 / 74 卷日期：

算法比赛模拟题精解之“Tairitsu and Dynamic Objects”

贡献者 | 郭达彬

简介：根据题意，分析得知，Hikari 和 Tairitsu 每次会优先选择 ai+bi 的值最大

的物品，当物品的 ai+bi 值相等时，选择 bi 大的那个。

题目描述

题目等级：容易

知识点：贪心

查看题目：Tairitsu and Dynamic Objects

Hikari 和 Tairitsu 面前有 n 个物品，这些物品编号为 1,2,...,n。

每个物品有两个属性。第 i 个物品的两个属性分别为 ai, bi。

初始 n 个物品均可被选取。Hikari 与 Tairitsu 会轮流选取当前可选取的物品中

的一个，并把它拿走，这个物品之后不可被选取。第一轮 Hikari 先选取。

设 Hikari 选取的物品编号的集合为 H，Tairitsu 选取的物品编号的集合为 T。

所有物品均被选取完之后，Hikari 得分为 ∑ ai(i ∈ H)；而 Tairitsu 得分为

  • bi(i ∈ T)。

Hikari 和 Tairitsu 都希望自己的得分比对方大，你需要求出双方都使用最优策略

的情况下，双方各会获得多少分。

注意：若对于某个人来说，剩余的物品中有多个对两人分数大小关系影响相同的

物品，那么他会优先选择 bi 最大的那个。

输入一个正整数 n，表示物品个数。

再输入两个数组 a 和 b，分别表示 n 个物品的 A 属性和 n 个物品的 B 属性。（保

证 1<=n<=2*1e5, 0<=ai,bi<=1e9）

输出一行，两个整数分别表示 Hikari 和 Tairitsu 的得分。

示例 1

输入：

5

[1,2,3,4,5]

[5,4,3,2,1]

输出：

[9,6]

解题思路：

根据题意，分析得知，Hikari 和 Tairitsu 每次会优先选择 ai+bi 的值最大的物

品，当物品的 ai+bi 值相等时，选择 bi 大的那个。

因此，可以对物品进行排序，排序有两个依据，优先依据 ai+bi 的值，然后是 bi

的值。降序排好后，Hikari 和 Tairitsu 依次按顺序选择物品，Hikari 先选择，选择好

以后，分别计算 Hikari 和 Tairitsu 的分数即可。

时间复杂度：O(n)

空间复杂度：O(1)

看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：Tairitsu and

Dynamic Objects

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”