【Split】

【问题描述】

初始时你有一个大小为S的细胞,每次你可以从你已有的细胞中选择一个大小不为1的细胞,设它的大小为Q,然后把它分裂成两个细胞a和Q-a,其中1≤a<Q且a为整数,这样你获得的收益是a*(Q-a)

给定S,M,求最少分裂几次才能得到至少M的收益。

【输入格式】

第一行两个正整数S,M

【输出格式】

输出一个非负整数表示答案

如果无法达到M的收益输出-1

【样例输入】

765 271828

【样例输出】

14

【数据范围】

对于30%的数据S≤10

对于100%的数据2≤S≤1000,1≤M≤10^9

这道题首先很容易想到的是一个每次对半分用优先队列选最大值的做法,然而这并没有什么卵用!

一个很简单的例子:10 32 虽然第一次分成5 5比分成3 7更优,可是第二次分成2 3 5的总收益为31而分成3 3 4的总收益为33,显然3 7开始第二步就更优了!

其实根据对基本不等式的感觉,可以大概猜到把S尽量均分得到的收益最大(不会证明233)。

考虑把S分成2份,显然收益最大值为Q^2/4=Q^2/2-2*(Q/2)^2/2

考虑把S分成3份,第一次收益W1=(Q/3)*(2Q/3)=2Q^2/9 第二次的收益W2=(Q/3)*(Q/3)=Q^2/9 W总=W1+W2=Q^2/3

考虑把S分成n份,可以推得W总=Q^2*(n-1)/2*n①

其实就是Q^2/2-(x^2+y^2+z^2+……+p^2)/2②,其中x=y=z=……=p=Q/n 两个公式等价但是最好用第二个公式,原因如下:

考虑比如把10分成4份这种除不尽的情况 此时先分成2 2 2 2 然后剩下的2为了均分分别加到其中2个2上去,变成2 2 3 3 然后再计算。(这时就不能用公式①,因为不能完全均分)

注意除号写的地方不好的话会因为整除挂掉二个点……我原来先除2就WA了,改成先减再除就AC了 一定是我脸太黑233

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*