#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<set>
#include<queue>
using namespace std;
struct Data {
	int F, position, t;
};
deque<Data>DPToDP;
deque<Data>DPToDPL;
deque<Data>DPLToDP;
deque<Data>DPLToDPL;
queue<Data>addT;
queue<Data>addL;
vector<int>DP;
vector<int>DPL;
vector<int>T;
vector<int>prefixSum_T;
int N, M;
bool JudgeFront_T(deque<Data>&que, const int ti) {
	if (que.size() == 1) {
		return 0;
	} else {
		Data node1 = que.front();
		que.pop_front();
		Data node2 = que.front();
		que.push_front(node1);
		if (node1.position == node2.position) {
			return 1;
		}
		if (node2.t == node1.t)
			return 0;
		if ((node2.F - node1.F) /
		    (node2.t - node1.t) <= ti)
			return 1;
		else
			return 0;
	}
}
bool JudgeBack_T(deque<Data>&que, const Data add) {
	if (que.size() == 1) {
		return 0;
	} else {
		Data node1 = que.back();
		que.pop_back();
		Data node2 = que.back();
		que.push_back(node1);
		if (node1.t == node2.t)
			return 1;
		if (add.t == node1.t)
			return 0;
		if ((node1.F - node2.F) / (node1.t - node2.t)
		    > (add.F - node1.F) / (add.t - node1.t))
			return 1;
		else
			return 0;
	}
}
bool JudgeFront_L(deque<Data>&que, const int i) {
	if (que.size() <= 1) {
		return 0;
	} else {
		Data node1 = que.front();
		que.pop_front();
		Data node2 = que.front();
		que.push_front(node1);
		if (node1.t == node2.t)
			return 1;
		if ((node2.F - node1.F) / (node2.t - node1.t) > i)
			return 1;
		else
			return 0;
	}
}
bool JudgeBack_L(deque<Data>&que, const Data add) {
	if (que.size() == 1) {
		return 0;
	} else {
		Data node1 = que.back();
		que.pop_back();
		Data node2 = que.back();
		que.push_back(node1);
		if (node1.t == node2.t)
			return 1;
		if (add.t == node1.t)
			return 0;
		if ((node1.F - node2.F) / (node1.t - node2.t)
		    > (add.F - node1.F) / (add.t - node1.t))
			return 1;
		else
			return 0;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	T.assign(N + 1, 0);
	DP.assign(N + 1, 0x3f3f3f3f);
	DPL.assign(N + 1, 0x3f3f3f3f);
	prefixSum_T.assign(N + 1, 0);
	for (int i = 1; i <= N; i++)
		cin >> T[i];
	sort(T.begin(), T.end());
	for (int i = 1; i <= N; i++)
		prefixSum_T[i] = prefixSum_T[i - 1] + T[i]/*, cout << T[i] << " "*/;
	//cout << "\n";
	DPToDP.push_back({0, 0, 0});
	for (int i = 1; i <= N; i++) {
		//cout << T[i] << " " << i << ":";
		/*if (T[i] == T[i - 1])
		  DP[i] = DP[i - 1];*/
		while (addT.empty() == 0 && T[i] - addT.front().position >= M) {
			//cout<<addT.top().F<<" "<<addT.top().position<<" "<<addT.top().t<<"\n";
			while (DPToDP.empty() == 0 && JudgeBack_T(DPToDP, addT.front()))
				DPToDP.pop_back();
			DPToDP.push_back(addT.front());
			addT.pop();
		}
		while (addL.empty() == 0 && T[i] - addL.front().position >= M) {
			while (DPLToDP.empty() == 0 && JudgeBack_T(DPLToDP, addL.front()))
				DPLToDP.pop_front();
			DPLToDP.push_back(addL.front());
			addL.pop();
		}
		while (DPToDP.empty() == 0 && JudgeFront_T(DPToDP, T[i]))
			DPToDP.pop_front();
		while (DPLToDP.empty() == 0 && JudgeFront_T(DPLToDP, T[i]))
			DPLToDP.pop_front();
		while (DPToDPL.empty() == 0 && (JudgeFront_L(DPToDPL, i) || T[i] + DPToDPL.front().t >= M))
			DPToDPL.pop_front();
		while (DPLToDPL.empty() == 0 && (JudgeFront_L(DPLToDPL, i) || T[i] + DPLToDPL.front().t >= M))
			DPLToDPL.pop_front();
		if (DPToDP.empty() == 0) {
			DP[i] = min(DP[i], DPToDP.front().F + T[i] *
			            (i - DPToDP.front().t) - prefixSum_T[i]);
			//cout << DPToDP.front().t << ":";
			//cout << DP[i] << " ";
		}
		if (DPLToDP.empty() == 0) {
			DP[i] = min(DP[i], DPLToDP.front().F + T[i] *
			            (i - DPLToDP.front().t) - prefixSum_T[i]);
			//cout << DPLToDP.front().t << ":";
			//cout << DP[i] << " ";
		}
		//cout<<"|";
		int TI;
		if (DPToDPL.empty() == 0) {
			if (DPL[i] > DPToDPL.front().F + i * (M - DPToDPL.front().t) - prefixSum_T[i]) {
				TI = -DPToDPL.front().t;
				DPL[i] = DPToDPL.front().F + i * (M - DPToDPL.front().t) - prefixSum_T[i];
			}
			//cout << DPToDPL.front().position << ":";
			//cout << DPL[i] << " ";
		}
		if (DPLToDPL.empty() == 0) {
			if (DPL[i] > DPLToDPL.front().F + i * (M - DPLToDPL.front().t) - prefixSum_T[i]) {
				TI = -DPLToDPL.front().t;
				DPL[i] = DPLToDPL.front().F + i * (M - DPLToDPL.front().t) - prefixSum_T[i];
			}
			//cout << DPLToDPL.front().position << ":";
			//cout << DPL[i] << " ";
		}
		if (DPToDPL.empty() == 0 || DPLToDPL.empty() == 0) {
			while (DPLToDPL.empty() == 0 && JudgeBack_L(DPLToDPL, {DPL[i] - i * (T[i] + M)
			        + prefixSum_T[i], i, -T[i]
			                                                      }))
				DPLToDPL.pop_back();
			DPLToDPL.push_back({DPL[i] - i * (T[i] + M) + prefixSum_T[i], i, -TI-M});
			addL.push({DPL[i] + prefixSum_T[i], TI+M, i});
		}
		if (DPToDP.empty() == 0 || DPLToDP.empty() == 0) {
			while (DPToDPL.empty() == 0 && JudgeBack_L(DPToDPL, {DP[i] - i * (T[i] + M)
			        + prefixSum_T[i], i, -T[i]
			                                                    }))
				DPToDPL.pop_back();
			DPToDPL.push_back({DP[i] - i * (T[i] + M) + prefixSum_T[i], i, -T[i]});
			addT.push({DP[i] + prefixSum_T[i], T[i], i});
		}
		//cout << "\n";
	}
	cout << min(DP[N], DPL[N]);
	return 0;
}

记录

两个推导式：

$\frac{DP_k+S_k-DP_j-S_j}{k-j} <T_i$

$\frac{DP_k-kT_k+S_k-km-(DP_j-jT_j+S_j-jm)}{-T_k-(-Tj)}<i$