[国家集训队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

发表回复

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