CFGYM102394E CCPC2019哈尔滨 E题 Exchanging Gifts

假设我们能维护出最终序列的长度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'

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据