题目:
http://cogs.pro/cogs/problem/problem.php?pid=1883
为了提高自己的实力,gx想要制定一个合理的刷题计划。这里我们用实数来表示题目的难度,并且把刷题计划中由题目难度组成的序列称为刷题序列。gx刷题最喜欢循序渐进的方式,最理想的情况莫过于刷题序列是个等差数列了。但是这很难做到,于是我们定义一个刷题序列a的偏离值
,其中L是给定的一个常数。
现在gx的老师已经布置给了他n道必做题,同时他还有空余时间从OJ上找m道题目来刷。他不希望改变这n道必做题的相对顺序,但是选做题的难度以及在数列中的位置都是任意的(OJ上的题目太多了,随你怎么挑)。
gx希望你帮他设计一个刷题序列,使得该序列的偏离值最小。
![[国家集训队2011]刷题计划 <wbr>解题报告” style=”height:auto; max-width:100%; vertical-align:middle; font-family:serif; font-size:16px; line-height:20px; background-color:rgb(255,255,255)”><span style=](http://47.95.244.138/wp-content/uploads/2017/10/sg_trans-1.gif)
现在gx的老师已经布置给了他n道必做题,同时他还有空余时间从OJ上找m道题目来刷。他不希望改变这n道必做题的相对顺序,但是选做题的难度以及在数列中的位置都是任意的(OJ上的题目太多了,随你怎么挑)。
gx希望你帮他设计一个刷题序列,使得该序列的偏离值最小。
分析:
其实这道题和“骑行川藏”很像,但它是11年的,当时后者还没出来……
首先明确一下题意。假设我们要在a[i]和a[i+1]之间放一些题,那必然是这样的: