C++14(g++5.4) 解法, 执行用时: 795ms, 内存消耗: 8276K, 提交时间: 2019-01-28 16:48:46

#include<algorithm>
#include<cstdio>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
long long m,l[1000010];
int n;
bool check(long long U)
{
    long long L=m,R=m;
    for(int i=2;i<=n;i++)
    {
        long long a=m-R,b=m-L;
        if(l[i]<=b)R=m;
        else R=m-(l[i]-b);
        a=U-m-a;b=U-m-b;swap(a,b);
        if(l[i]<=b)L=U-m;
        else L=min(U-m,m-(l[i]-b));
        L=max(0ll,m-L);
    }
    return m-L>=l[1];
}
int main()
{
    int T;
    for(scanf("%d",&T);T--;)
    {
        scanf("%d%lld",&n,&m);
        bool flag=1;
        long long L=-1,R=3*m+1;
        rep(i,n)
        {
            scanf("%lld",&l[i]);
            if(l[i]>m)flag=0;
            L=max(L,l[i]+m-1);
        }
        if(!flag)
        {
            puts("-1");
            continue;
        }
        for(;L<R-1;)
        {
            long long mid=(L+R)>>1;
            if(check(mid))R=mid;else L=mid;
        }
        printf("%lld\n",R);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 689ms, 内存消耗: 42288K, 提交时间: 2018-12-21 15:44:41

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = (int)1e6 + 1;
int t, n;
LL m, dt[maxn], low[maxn], upp[maxn];
bool check(LL tot) {
	low[0] = upp[0] = m;
	for(int i = 1; i < n; ++i) {
		low[i] = m - min(tot - m - max(dt[i] - upp[i - 1], 0LL), m);
		upp[i] = m - max(dt[i] - (m - low[i - 1]), 0LL);
		if(low[i] > upp[i])
			return 0;
	}
	return m - low[n - 1] >= dt[0];
}
int main() {
	scanf("%d", &t);
	while(t--) {
		scanf("%d%lld", &n, &m);
		LL L = m, R = m;
		for(int i = 0; i < n; ++i) {
			scanf("%lld", dt + i);
			L = max(L, m + dt[i]);
			R = max(R, m + dt[i] + dt[i]);
		}
		if(R + R > L + L + L) {
			puts("-1");
			continue;
		}
		while(L < R) {
			LL M = (L + R) >> 1;
			if(check(M)) {
				R = M;
			} else {
				L = M + 1;
			}
		}
		printf("%lld\n", L);
	}
	return 0;
}