开发者社区> 问答> 正文

遇到一个分数问题,求解答。

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 的得分。

展开
收起
游客4skzfvnrxrzbi 2021-12-23 16:36:37 559 0
1 条回答
写回答
取消 提交回答
  • 根据题意可知,分析得知,Hikari和Tairitsu每次会优先选择ai+bi的值最大的物品,当物品的ai+bi值相等时,选择bi大的那个。因此,可以对物品进行排序,排序有两个依据,优先依据ai+bi的值,然后是 bi的值。降序排好后,Hikari 和 Tairitsu 依次按顺序选择物品,Hikari 先选择,选择好以后,分别计算 Hikari 和 Tairitsu 的分数即可。 输入:5 [1,2,3,4,5] [5,4,3,2,1] 输出:[9,6]

    2021-12-23 18:29:57
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载