假设我们能维护出最终序列的长度L和最终序列出现最多的数的个数cnt,假设$cnt\leq\frac L 2$ ,那么答案是L,这时候我们把序列升序和降序对起来就构造出n的结果。 假设$cnt>\frac L 2$,那么答案是$2(L-cnt)$,我们仍然把序列升序和降序对应起来,答案是$L-(cnt-(L-cnt))=2*(L-cnt)$ 比如 1 2 3 3 3 3 3 3 3 3 3 3 2 1 中间有3个3是重了的,那么重的部分有cnt-(L-cnt)个,其中L-cnt表示的是1 2的长度,所以总答案是L-(cnt-(L-cnt)) 现在的问题在于如何维护出这个众数,并且判定$cnt\leq \frac L 2$是否成立。 考虑一种线性时间求求序列众数(出现次数大于一半)的方法: 令f(i)表示我们从头开始扫到第i个元素的时候(用$a_i$表示),序列中出现次数最多的数与其他的数出现次数之和的差值。同时我们需要维护这个数是多少(用x来表示)。 每次扫到$a_i$的时候: - 如果$a_i=x$,那么f(i)=f(i-1)+1,x不变 - 如果$a_i\neq x$,那么f(i)=f(i-1)-1,然后如果$f(i)<0$,那么x变为$a_i$,同时$f(i)$取反。 对于这个题,如果我们要使用这种求众数的方法,核心在于如何考虑操作2(合并两个序列时)如何处理。 我们维护每个序列的f和x,合并两个序列的时候: - 如果他们的f相同,那么新序列的f不变,x相加。 - 如果他们的f不同,那么考虑下两个序列的哪一个的x比较大。如果他们相同,那么新序列的f就写为0(这时候可能存在两个众数),x从原来的x里随便选一个。如果他们不同,那x选择为f较大的那一个,同时f设置为较大值减掉较小值。 所以对于这个题,我们先用这种求众数的方法算出来最终序列的众数。 但此时求出来的众数,仅仅是在保证存在一个出现次数超过序列长度一半时候的众数,如果不存在这样子的众数,也会得出来一个结果,但是并不具有意义。 所以我们再跑一遍递推,求出来我们上一步求的众数的出现次数,然后我们就可以照着前文所述来算答案了。 *此外,这个题卡常* 我跑了半天性能分析后大概知道了几个卡常的点: 1. 输入量非常巨大,请考虑一次性读入输入数据后自行用缓冲区处理输入。 2. std::vector的构造函数非常慢(性能分析显示,$10^6$次调用大约花了80ms),所以不要使用vector来存储变长的序列,考虑自行分配-回收内存。 3. State结构体的构造函数占了大概40ms的时间,考虑强制内联。 另外,读入函数千万不要写错了!不要写成chr>='9'!