开发者社区> 问答> 正文

遇到一个组队问题,求解答

H大学迎来了一年一度的羽毛球双打比赛,小伙伴们都很积极地报了名。但是为了达到 1 ⊕ 1>1(注:a ⊕ b>max(a,b))的效果,学校给每位同学进行了实力认证,每位同学都获得了一个能力值。在组队的时候,组成队伍的两位同学的能力值 a,b 必须满足条件:a ⊕ b>max(a,b)。校长想要统计一共可以组成多少不同的队伍,请你帮助校长计算出来。输入学生数 n(2<=n<=10^5) 和 n 个正整数 ai(1<=ai<=10^9),表示每位同学能力值。

展开
收起
游客4skzfvnrxrzbi 2021-12-23 17:09:18 463 0
1 条回答
写回答
取消 提交回答
  • 根据题意,本题需要找出符合 a⊕b>max(a,b) 条件的队伍,如果使用两重循环,两两判断学生是否符合条件,会超出时间限制。本题的约束条件a ⊕ b>max(a,b)中,假设a<b,b=1001(该数字为二进制形式),从右往左数,可以发现数字b 的第二位和第三位为0,若a想要满足约束条件和 b组队,数字a的最高位必须为数字 b值为0 的对应的位,即第二位和第三位,若 a 等于 100 或 10,均可以满足条件和 b 组队。理解了上一步之后,可以统计每个数字中0出现位置,比如第三位是 0 的数字在数组中有多少。用 HashMap 进行存储,以0的位置为key,对应位置为 0 的数字的数量为value。统计完所有0出现的次数后,遍历数组,计算每个数字的二进制的位数,在HashMap中取出对应的 value。在遍历数组的过程中,对所有取出的 value 值求和即可得到可以组成的队伍总数。输出一个整数,表示一共可以组成的队伍总数。 因此输入:5 [1,2,3,4,5] 输出:6

    2021-12-23 19:05:34
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
用心聆听,服务见智 立即下载
分身大师那些事 立即下载
分身大师那些事儿 立即下载