问题 019：选择卡片1 (难度：中等) 竞技编程-提高思维

题目描述 有 N 张卡片，每张卡片的颜色由整数 A1, A2, ..., AN 表示。

• 当 Ai = 1 时，卡片是红色；
• 当 Ai = 2 时，卡片是黄色；
• 当 Ai = 3 时，卡片是蓝色。

任务是计算选择相同颜色的两张卡片的方法有多少种。

输入格式

• 第一行包含一个整数 N (2 ≤ N ≤ 500000)，表示卡片的数量。
• 第二行包含 N 个整数 A1, A2, ..., AN (1 ≤ Ai ≤ 3)，表示卡片的颜色。

输出格式

• 输出一个整数，表示选择相同颜色的两张卡片的方法的数量。

示例

​输入示例 1​：

6
1 3 2 1 1 2

​输出示例 1​：

4

解释 共有 4 种方式可以选择两张相同颜色的卡片：

• 选择第 1 张卡片和第 4 张卡片（红色）；
• 选择第 1 张卡片和第 5 张卡片（红色）；
• 选择第 4 张卡片和第 5 张卡片（红色）；
• 选择第 3 张卡片和第 6 张卡片（黄色）。

时间复杂度分析 为了计算组合数，首先需要统计每种颜色的卡片数量，然后根据组合公式 C(n, 2) = n * (n - 1) / 2 来计算每种颜色选择两张卡片的方式。由于只涉及三种颜色的卡片计数，时间复杂度为 O(N)，适合处理大规模数据。

• ​计算组合数​：对于每种颜色，若该颜色的卡片数量大于等于 2，则根据组合公式 C(n, 2) = n * (n - 1) / 2 计算可以选择的卡片对数，并将其加到结果中。
• ​输出​：最后输出所有颜色的卡片对数之和。

时间复杂度：

• 时间复杂度为 O(N)，其中 N 是卡片的数量。遍历所有卡片并统计每种颜色的数量，然后计算组合数。这种方式足以处理最大输入限制 N = 500000。