AcWing-109.天才ACM
¶首先来首歌曲来放松一下吧!
题目链接:109. 天才ACM
¶题目背景:
又是一道好题,参考了许多题解,明白后,有因为粗心,debug了好久才AC了!
¶题目描述
给定一个整数 M,对于任意一个整数集合 S,定义“校验值”如下:
从集合 S 中取出 M 对数(即 2∗M 个数,不能重复使用集合中的数,如果 S 中的整数不够 M 对,则取到不能取为止),使得“每对数的差的平方”之和最大,这个最大值就称为集合 S 的“校验值”。
现在给定一个长度为 N 的数列 A 以及一个整数 T。
我们要把 A 分成若干段,使得每一段的“校验值”都不超过 T。
求最少需要分成几段。
¶输入格式
第一行输入整数 K,代表有 K 组测试数据。
对于每组测试数据,第一行包含三个整数 N,M,T 。
第二行包含 N 个整数,表示数列A1,A2…AN。
¶输出格式
对于每组测试数据,输出其答案,每个答案占一行。
¶数据范围
1≤K≤12
1≤N,M≤500000
0≤T≤1018
0≤Ai≤220
¶输入样例:
1 |
|
¶输出样例:
1 |
|
¶题目分析:
¶题目要求:
校验值:就是每对数的差的平方之和
将一个序列分成若干段,使得每一段的校验值都不超过T,求可分成的最小段数!
每一段要取出M对数,即2 * M 个数,取到不能取为止!
¶解题思路:
贪心 + 归并(只用到合并) + 倍增
首先一段的校验值最大,很简单,直接排序后,取一个最大值和一个最小值,每次都去最大最小即可,这样贪心得到的校验值就是这一段的最大值!(当然不能重复取!)
如何可以使得段数尽可能的小了?
那么一段要取多长?
我们可以进行二分,每次都将二分得到的区间计算的到的校验值和T比较即可,然后动态的改变右端点!
但是这样得到的区间要想计算校验值,得进行该序列的排序,用到sort,复杂度石灰超时的!
这是可以用倍增来解决这个问题!
要想使段数尽可能少,则要保证每一段在不超过T的情况下,尽可能的长!
用 l 和 r 指向区间的左右端点,若区间不超过T,就进行倍增拓展长度(p),p 成倍增加,r 也要一直后移;若某次成倍增加是校验值超过T,则当前p就得成倍减少,直到p为0,此时就是说明找到了不超过T的最大长度!
第一段开始,已排序序列b数组需要和那段倍增的长度进行拓展,需要进行排序,但是 b 数组已经有序,根本不需要去整段去排序,将倍增长度排序后,直接使用归并进行两个序列的合并,得到一个新数组即可!
其后的每一段合并时,b数组都是排好序的,这样可以大大减少时间消耗!
b数组用来保存处理过的序列,c数组来保存每次倍增多出来的序列,temp数组来保存b和c合并后的序列!
若当前序列不超过T,则将合并后的序列temp归还给b数组(表示处理过且当前是有序序列),返回true,右端点右移到倍增后的位置,p继续倍增!
若当前序列超过了T,则直接返回false,此时b数组的存储没有被改变,然后p倍减!
为什么会比二分更优化呢?
因为每次的b数组都是有序的,不需要排序,省了很多时间!
可以参考代码中的注释进行详细了解!
也可以参考如下的一篇题解!
¶题解:
注意:
校验值可能会溢出,要使用long long!
以防倍增后使右端点溢出,使用t = min(r + p, n - 1)
来进行约束!
每一段找到右端点后,当前段在b数组就是有序的!
1 |
|