【题解】CF1426C Increase and Copy

题目

CF1426C Increase and Copy

题解

此题关键在于一个简易的贪心:先进行+1操作,再进行复制操作(证明:若交换一个排在前面的+1操作和一个排在后面的复制操作,总和不会变大)。若先进行a次+1操作,再进行b次复制操作,则会得到一个由(b+1)个(a+1)组成的数列。枚举数列中的数x的大小,答案取最小值。

由于答案的形式与对勾函数比较相似,所以答案接近于根号sum,可以减小枚举的范围。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年10月16日 下午10:49

【小白解析】
此题化繁为简的贪心思想可谓超凡脱俗。进行基本论证前需要声明贪心条件:

先进行+1操作,再进行复制操作(证明:若交换一个排在前面的+1操作和一个排在后面的复制操作,总和不会变大)

为基本常识。换句话说,对于两种+1操作和复制操作数量均相同样的方法,能取得最大值的一定是先将数组中唯一的元素加至最大,随后将其复制(该操作相当于把初始值复制完毕以后,对每一个元素同时进行+1操作,为伤害等同于单体的无差别AOE)。
在该前提下,问题变成了进行a次+1操作,得到数字a+1后,放大多少倍即可使数组元素和不小于n:

若先进行a次+1操作,再进行b次复制操作,则会得到一个由(b+1)个(a+1)组成的数列。

即:(a+1)*(b+1)>=n
该情况下 b>=n/(a+1)-1。b应当向上整取。在实际算法中,a+1对应i;b+1对应(int)ceil((double)sum/i), ceil()用于向上整取;-2用于获取操作次数。
该函数最为出神入化的一点在于对柯西不等式(或者其他什么数学关系)的运用:

由于答案的形式与对勾函数比较相似,所以答案接近于根号sum,可以减小枚举的范围。

由于我们得知最佳情况下(a+1)*(b+1)==n,当n为定值时,a==b时a+b最小。即a+1==b+1==sqrt(n),对应第7行的初始化(具体情况下需要-1,以防止(int)操作造成小数缺失,导致误差);随后遍历i至sqrt(n)+1(原因同上)。最后得到的最小和即为所求值。
*只需要遍历3次,不得不说惊世骇俗。