题目传送门
在场上被骗了，最后才写出来，遂有此题解。
题意分析
记原题面中 \(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 代码
//#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;
}