在场上被骗了，最后才写出来，遂有此题解。
题意分析
记原题面中 $L,M$ 分别为 $l,m$。
如果无解则输出
Che_is_Loser。
然而你发现似乎怎样都有解，实际上也是如此……也许只有我在这里停了。
但是在 IOI 赛制下，其实你可以直接交一发就可以知道没有无解了。
我们的目标是让 $a_1,a_2,\cdots,a_n$ 都增长到 $m$。那么对于每一个 $a_i<m$，对答案的贡献至少是 $m-a_i+1$。因为你至少选择 $1$ 次，再每次增长 $1$。
-
容易想到如果存在 $a_x\geq m$，无论 $l$ 为何值，你始终有一种最优策略，即从 $x$ 向两边扩展。实际上的操作次数也就是： \(\textit{cnt}+\sum_{i=1}^n\max(m-a_i,0)\)
$\textit{cnt}$ 表示 $a_i<m$ 的数量。
这个策略是最优的，因为这就是上文的下界。
-
对于不存在 $a_x\geq m$ 的情况，考虑贪心。
不难发现 $\displaystyle\sum_{i=1}^n\max(m-a_i,0)$ 的贡献是不可避免的，因此总次数最小当且仅当每一个点被重复选择的次数最小。
-
如果构造出了 $a_x\geq m$，则剩余的每一个点的选择次数都为 $1$，最优。
-
如果不是先构造 $a_x\geq m$，则不优。
证明也比较简单。你肯定会有一个点 $y$ 是最先达到 $m$ 的，之后你就可以从 $y$ 开始扩展。但是如果除了 $y$ 之外你还使 $z$ 增长，那么之后 $y$ 扩展的时候又要选择一次 $z$，$z$ 被重复选择，不优。
因此思路就很简单：用最少的选择次数构造一个 $a_x\geq m$。不难想到选择 $a$ 的最大值来构造。
对于最大值 $a_x$，取其相邻项 $a_y$。（$y=x\pm1$）
先选择 $a_y$，再令其增长 $a_y\leftarrow a_x+1$。这一次对于答案的贡献为 $a_x+1-a_y+1$。
之后就是 $a_x\leftarrow a_y+1$，再 $a_y\leftarrow a_x+1$，重复循环。
每次对于答案的贡献为 $3$，$a_x$ 或 $a_y$ 增长 $2$。
得到了 $a_x=m$ 之后，继续扩展即可。
-
时间复杂度 $\mathcal O(n)$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
#define int ll
constexpr const int N=1e6;
int n,l,m,a[N+1],d[N+1];
int left_max[N+1],right_max[N+1];
int ans;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>l>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
ll sum=0;
int cnt=0;
bool vis=false;
for(int i=1;i<=n;i++){
d[i]=max(0ll,m-a[i]);
sum+=d[i];
if(d[i]>0){
cnt++;
}
if(a[i]>=m){
vis=true;
}
}
if(sum==0){
cout<<"0\n";
return 0;
}
if(vis){
cout<<sum+cnt<<'\n';
return 0;
}
int Max=a[1],x=1;
for(int i=1;i<=n;i++){
if(a[i]>Max){
Max=a[i];
x=i;
}
}
int ans=0,y=x+1;
if(y>n){
y=x-1;
}
ans+=1+a[x]+1-a[y];
a[y]=a[x]+1;
while(a[y]<m){
swap(x,y);
a[y]+=2;
ans+=3;
}
sum=0;cnt=0;
for(int i=1;i<=n;i++){
d[i]=max(0ll,m-a[i]);
sum+=d[i];
if(d[i]>0){
cnt++;
}
}
ans+=cnt+sum;
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
