{"problem":{"name":"「GLR-R3」惊蛰","description":{"content":"比赛临近，各式测试也丰富了起来，作为天依他们的专业分析师，你的工作是统计分析队员们表现情况——总之，某领导要来慰问，所以你被要求修改出一份令人赏心悦目的分析报告。 在已有的 $n$ 次测试中，对于某位特定的选手，他在第 $i$ 次测试的**波动值**是非负整数 $a_i$。波动值越小表示选手在测试中的心态和发挥越稳定，所以你需要“略微调整”波动值序列 $\\{a_n\\}$，得到另一个非负整数序列 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8476"},"statements":[{"statement_type":"Markdown","content":"比赛临近，各式测试也丰富了起来，作为天依他们的专业分析师，你的工作是统计分析队员们表现情况——总之，某领导要来慰问，所以你被要求修改出一份令人赏心悦目的分析报告。\n\n在已有的 $n$ 次测试中，对于某位特定的选手，他在第 $i$ 次测试的**波动值**是非负整数 $a_i$。波动值越小表示选手在测试中的心态和发挥越稳定，所以你需要“略微调整”波动值序列 $\\{a_n\\}$，得到另一个非负整数序列 $\\{b_n\\}$。不过，做人不能昧良心，但报告又必须好看，所以 $\\{b_n\\}$ 有如下要求：\n\n- $\\{b_n\\}$ **单调不递增**，选手越来越厉害嘛；\n\n- 对于每个 $i$，如果 $b_i<a_i$，老师会不高兴，所以你需要花费 $C$ 单位的精力说服老师（其中 $C$ 为给定常数）；\n- 对于每个 $i$，如果 $a_i\\le b_i$，选手会不高兴，而且可能很不高兴，所以你需要花费 $b_i-a_i$ 单位的精力安慰选手。\n\n你希望在满足条件的情况下，**最小化**花费的精力之和。作为成熟的信竞选手，你自然需要自己动手，求出这一最小化的结果。\n\n#### 形式化题意\n\n给定非负整数序列 $\\{a_n\\}$，定义函数 $f(x,y)$ 为\n\n$$\nf(x,y)=\\begin{cases}\nx-y,&x\\ge y\\\\\nC,&x< y\n\\end{cases},\n$$\n\n其中 $C$ 是给定常数。请构造一个**不增**非负整数序列 $\\{b_n\\}$，最小化\n\n$$\n\\sum_{i=1}^nf(b_i,a_i).\n$$\n\n你仅需输出这一最小化的结果。\n\n## Input\n\n第一行两个整数，表示序列长度 $n$ 和给定常数 $C$。\n\n接下来一行表示序列 $\\{a_n\\}$ 。\n\n## Output\n\n输出一行一个整数，表示最小化的结果。\n\n[samples]\n\n## Background\n\n&emsp;&emsp;「微雨众卉新，一雷惊蛰始」\n\n---\n\n&emsp;&emsp;中午，休息室，阿绫肩膀上。\n\n&emsp;&emsp;“我有一个愿望，参加全国音乐祭，获奖，和阿绫一起，摆脱这训练的苦海。”\n\n&emsp;&emsp;“为热爱而到来，为抽身而努力……吗”。\n\n&emsp;&emsp;正午的阳光渗过窗帘，抚上困倦的人儿的脸颊。天依的左手悄悄搭上阿绫怀里的吉他，\n\n&emsp;&emsp;“铮——”\n\n&emsp;&emsp;蛰虫被雷声唤醒，没人向他们保证雨的降临。\n\n---\n\n&emsp;&emsp;**惊蛰**&emsp;「我愿把岁月磨成望镜寻遍这星空　将微光聚焦手心紧紧握住不放松」\n\n## Note\n\n#### 样例 #1 解释\n\n构造 $\\{b_n\\}=\\{5,5,2\\}$，可见：\n\n$$\n\\begin{aligned}\n\\sum_{i=1}^nf(b_i,a_i) &=  f(5,4)+f(5,5)+f(2,2)\\\\\n&= 1+0+0\\\\\n&= 1.\n\\end{aligned}\n$$\n\n#### 样例 #2 解释\n\n构造 $\\{b_n\\}=\\{12,11,4,2,1,1,1,1,1,1\\}$，可以得到答案。\n\n### 数据规模与约定\n\n**本题采用 Subtask 的计分方式。**\n\n设 $V$ 为序列 $\\{a_n\\}$ 中元素以及常数 $C$ 的值域。\n\n对于 $100\\%$ 的数据，$1\\le n\\le10^6$，$V\\subseteq[0,10^9]$。\n\n对于不同的子任务，作如下约定：\n\n| 子任务编号 |   $n$   |       $V$       | 特殊性质 | 子任务分值 |\n| :--------: | :-------: | :-------------: | :------: | :--------: |\n|    $1$     | $\\le10^3$ | $\\subseteq[0,10^9]$ |    无    |    $25$    |\n|    $2$     | $\\le10^5$ | $\\subseteq[0,10^2]$ |  无   |    $15$    |\n|    $3$     | $\\le10^6$ | $\\subseteq[0,10^9]$ |  **A**   |    $5$    |\n|    $4$     | $\\le10^6$ | $\\subseteq[0,10^9]$ |  **B**   |    $15$    |\n|    $5$     | $\\le10^5$ | $\\subseteq[0,10^9]$ |  无   |    $20$    |\n|    $6$     | $\\le10^6$ |   $\\subseteq[0,10^9]$   |    无    |    $20$    |\n\n- **特殊性质 A**：对于常数 $C$ ，满足 $C = 0$。\n- **特殊性质 B**：对于序列 $\\{a_n\\}$ ，满足元素单调**递增**。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8476","tags":["动态规划 DP","线段树","二分","洛谷原创","O2优化","动态规划优化","洛谷月赛"],"sample_group":[["3 3\n4 5 2","1"],["10 5\n12 17 20 2 0 1 13 6 10 1","26"]],"created_at":"2026-03-03 11:09:25"}}