遇到一个组队问题，求解答
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)，表示每位同学能力值。
写回答
-
根据题意，本题需要找出符合 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赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
