CF1163B1 Cat Party (Easy Edition) 题解

yyycj · 2024-12-20 21:57:09 · 题解

原题跳转

CF1163B1 Cat Party (Easy Edition)

题目简述

给定序列 u，要求 u_{1} \sim u_{x} 在必须去掉一个元素后，使所有的数字出现次数相同，求 x 的最大值。

主要思路

首先，先要明确可以满足条件的四种序列：

• 所有元素均相同。
• 所有元素各不相同。
• 只有一个元素的出现次数为一，其他全部相同。
• 所有元素的出现次数均相同，只有一个比其他出现次数大一。

要判断这些情况，可以用一个计算每个元素出现次数和一个统计每种出现次数的出现次数的 map（这里可能有些绕，主要意思是假如有三个 1 和三个 2，那么 map 中的键为 3，对应的值为 2，表示出现次数为 3 的元素有 2 个），map 的好处就是自动排序且可以获得长度。

处理数组和 map

由于是从第一个元素开始，所以可以边读入边操作。

每次多增加一个元素，那么这个元素在增加之前的出现次数的出现次数就会少 1。

但是如果这个元素是第一次出现，那么元素出现次数 0 的出现次数就会被减少，所以需要特判；或者在删除后，如果这个元素增加之前的出现次数的出现次数等于 0 的话，就需要在 map 中删除，这两种情况如果不判断会让长度出现问题。

随后将元素出现个数增加后出现次数的出现次数加 1。

判断所有元素是否均相同

如果出现了这种情况，就说明输入的 i 个元素全部相同，那么 map 的长度一定为 1，且唯一的元素的键为 i，值为 1（值无需判断），表示出现次数为 i 的数有 1 个。

判断所有元素是否各不相同

如果出现了这种情况，那么 map 的长度也为 1，且唯一的元素的键为 1，值为 i（值无需判断），表示出现次数为 1 的数有 i 个。

判断是否只有一个元素的出现次数为一，其他全部相同

如果出现了这种情况，那么 map 的长度一定为 2，且由于 map 自动排序的特性，第一个元素的键和值一定都为 1，表示有出现次数为 1 的有 1 个。

判断是否所有元素的出现次数均相同，只有一个比其他出现次数大一

如果出现了这种情况，那么 map 的长度也为 2。由于 map 自动排序的特性，第二个元素的键一定比第一个元素的键大 1，且值为 1，表示比其他元素出现次数大 1 的有 1 个。

AC Code