题目链接

https://codeforces.com/problemset/problem/1000/B

题目大意

n个时刻，每到一个时刻，台灯的状态就反转一次。允许插入一个时刻（整数），使得亮的时间最长。所有时刻为0，a1，a2，……，an，M。

解题思路

插入位置只能是ai的相邻的位置，a(i)-1或者a(i)+1，但是如果a(i)-1==a(i-1)或者a(i)+1==a(i+1)，显然这俩位置是不能插入的。
几幅图说明灯亮总时间的变化：
红色代表亮，绿色代表不亮。
k插到a3之前，即a(3)-1的位置，注意在插入k点前，a3为暗转换点（即经过a3变暗），此时0 ~ M过程中亮灯的总时间为：插入k点后a3前面的亮灯时间=插入k点前a3前面亮灯时间相同-1；插入k点后a3后面的亮灯时间=插入k点前暗灯时间=a3 ~ M的总时间-插入k点前a3 ~ M点的亮灯时间。
我们用sum[i]表示第i个转换点之前的亮灯时间，那么就可以得到：（sum[n+1]为0 ~ M的时间，即M）
当插入点为暗转换点之前时，其插入后亮灯总时间为 (M-a[i])-(sum[n+1]-sum[i])+(sum[i]-1)

假如k插在了暗转换点之后，我们可以发现亮灯总时间与插在暗转换点之前的时间是一样的，也为 (M-a[i])-(sum[n+1]-sum[i])+(sum[i]-1)
综上，如果插入点为暗转换点的相邻点，那么总时间为 (M-a[i])-(sum[n+1]-sum[i])+(sum[i]-1)

如果插入点k插在了亮转换点相邻的位置呢？
我们可以得到总时间为 (M-a[i])-(sum[n+1]-sum[i])+(sum[i]+1)，唯一不同点在于+1还是-1。（不再证明了）
特殊情况：
要是a(i-1)+1==a(i)-1的情况呢？

也没什么问题，这只能说明k插在绿框1位置的总时间=插入在绿框2总时间，绿框2总时间=绿框3总时间，等量代换，绿框1，2，3总时间相等，仅此而已。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int a[N],sum[N],n,M;
vector<int> canins;//can insert的简写，存储可以插入的位置k，与k相邻的ai的索引i。有一点点离散化的思想
int main()
{
    cin>>n>>M;
    a[0]=0,a[n+1]=M,sum[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i&1) sum[i]=sum[i-1]+a[i]-a[i-1];//求sum，若为暗转换点
        else sum[i]=sum[i-1];//若为亮转换点
    }

    if(n&1) sum[n+1]=sum[n];//最后的M是亮转换点
    else sum[n+1]=sum[n]+M-a[n];//最后的M是暗转换点

    for(int i=1;i<=n;i++)
    {
        if(a[i]-1==a[i-1] && a[i+1]==a[i]+1) continue;//如果原转换点存在相邻，那就不能在某些转换点的相邻位置插入k
        canins.push_back(i);
    }
    if(a[n+1]-1!=a[n])canins.push_back(n+1);//判断是否能插到M之前的相邻位置
    //我想提醒一点，无需在0后面插入k，即无需在时刻为1的时候插入k，因为这种情况必然没有在a1前面相邻位置插入k好，即没有在ai-1时刻插入k好。自己理解。
    int ans=sum[n+1];//！
    for(int i=0;i<canins.size();i++)
    {
        if(canins[i]&1)//暗转换点
        ans=max(ans,(M-a[canins[i]])-(sum[n+1]-sum[canins[i]])+(sum[canins[i]]-1));
        else//亮转换点
        ans=max(ans,(M-a[canins[i]])-(sum[n+1]-sum[canins[i]])+(sum[canins[i]]+1));
    }

    cout<<ans<<endl;

    return 0;
}

总结

唉，好可惜，思路全对，证明也全都证明出来了，过了22样例，还是wa了，实现还是有问题。
再说一点，网上很多一个n+1次的循环，一个求时间的公式：ans=max(ans,(M-a[canins[i]])-(sum[n+1]-sum[canins[i]])+(sum[canins[i]]-1));就求出来的，不是很能理解，或许是他们蒙对的，又或许是他们推导出来了。
这里稍微用了点离散化的思想，通过前缀和实现的离散化，因为前缀和的下标是相对位置。不管怎么说，感觉这个题自己的思路居然这么清晰，真的信心爆棚，大佬放过我吧TAT！！！