[国家集训队2011]刷题计划 解题报…

题目:

http://cogs.pro/cogs/problem/problem.php?pid=1883

为了提高自己的实力,gx想要制定一个合理的刷题计划。这里我们用实数来表示题目的难度,并且把刷题计划中由题目难度组成的序列称为刷题序列。gx刷题最喜欢循序渐进的方式,最理想的情况莫过于刷题序列是个等差数列了。但是这很难做到,于是我们定义一个刷题序列a的偏离值 ,其中L是给定的一个常数。

现在gx的老师已经布置给了他n道必做题,同时他还有空余时间从OJ上找m道题目来刷。他不希望改变这n道必做题的相对顺序,但是选做题的难度以及在数列中的位置都是任意的(OJ上的题目太多了,随你怎么挑)。

gx希望你帮他设计一个刷题序列,使得该序列的偏离值最小。
分析:
其实这道题和“骑行川藏”很像,但它是11年的,当时后者还没出来……
首先明确一下题意。假设我们要在a[i]和a[i+1]之间放一些题,那必然是这样的:
[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a><br />
新放进去这些题目的难度一定均分了a[i]~a[i+1]之间的部分(图画的不太平均,不要在意这些细节)。</div>
<div>为什么呢?</div>
<div>
</div>
<div>假设某一段的长度为c,我们试图在中间加一道题,把它分成两段a,b,自然a+b=c。</div>
<div>其代价为:</div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a><br />
a+b=c,所以当a=b时a^2+b^2最大,代价最小。</div>
<div>所以相邻两段相等时代价最小。用调整法可以证明,在a[i]~a[i+1]之间放题一定是均分才能使代价最小。</div>
<div>(当然你也可以用柯西不等式证明)</div>
<div>
</div>
<div>所以题目就变成了:将这N-1段分别进行均分,使得新插入的点数之和<=M,并且代价最小。</div>
<div>(至于M道题中没有用上的部分,可以接在最后一道后面成为等差数列,其代价为零)</div>
<div>
</div>
<div>像“骑行川藏”一样,我们来考虑每一段的代价。</div>
<div>假设我们把长度d的一段(注意d可能为负)均分成了k段,代价是:</div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a></p>
<p>如果分成k+1段,代价是:</p></div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a></p>
<p>因此,从k段变成k+1段会让代价增加:</p></div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a><br />
随着k增加,这个值会逐渐增大(也就是说对代价的改进值越来越小)。</div>
<div>
</div>
<div>所以可以设想出一个这样的算法:一开始每一段都分成了1份。然后对于M次操作,每次选取增量最小的(也就是改进值最大的)一段,在其中多加一个点。</div>
<div>
</div>
<div>但是M非常大,怎么办?</div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a></p>
<p>
假设一开始增量的分布是这样的(y坐标代表增量的值,蓝线是0)</div>
<div>在结束时,增量可能是这样的:</div>
<div><a target=[国家集训队2011]刷题计划 <wbr>解题报告” title=”[国家集训队2011]刷题计划 <wbr>解题报告”></a><br />
由于每次都让最小的增量变大,所以大致是这样的,所有增量都不小于某个值。增量的变大是不连续的,所以可能会在红线之上。</div>
<div>
</div>
<div>算法就很好办了:二分结束时的最小增量,然后计算每一段被分成了多少份。好像没什么奇怪的细节……</div>
<div>
</div>
<div>
</div>
<div><strong>代码:</strong></div>
<div><a target=

http://cogs.pro/cogs/submit/code.php?id=143714

发表评论

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