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 的得分。
根据题意可知,分析得知,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]
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。