#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<queue>
using namespace std;
struct Data {
	long long F, position;
};
struct Data_Q {
	long long F, position, t;
};
deque<Data>que;
deque<Data_Q>q;
queue<Data>add;
vector<long long>DP;
vector<int>Sum;
vector<int>T;
int N, M;
bool JudgeFront(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 ((node2.F - node1.F) / (node2.position - node1.position) < ti)
			return 1;
		else
			return 0;
	}
}
bool JudgeFront_Q(const int&ti) {
	if (q.size() == 1) {
		return 0;
	} else {
		Data_Q node1 = q.front();
		q.pop_front();
		Data_Q node2 = q.front();
		q.push_front(node1);
		if (node1.t == node2.t)
			return 1;
		if ((node2.F - node1.F) / (node2.t - node1.t) < ti)
			return 1;
		else
			return 0;
	}
}
bool JudgeBack(const Data newNode) {
	if (que.size() == 1) {
		return 0;
	} else {
		Data node1 = que.back();
		que.pop_back();
		Data node2 = que.back();
		que.push_back(node1);
		if ((newNode.F - node1.F) / (newNode.position - node1.position)
		    < (node1.F - node2.F) / (node1.position - node2.position)) {
			return 1;
		} else
			return 0;
	}
}
bool JudgeBack_Q(const Data_Q newNode) {
	if (q.size() == 1) {
		return 0;
	} else {
		Data_Q node1 = q.back();
		q.pop_back();
		Data_Q node2 = q.back();
		q.push_back(node1);
		if (newNode.t == node1.t)
			return 0;
		if ((newNode.F - node1.F) / (newNode.t - node1.t)
		    < (node1.F - node2.F) / (node1.t - node2.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);
	Sum.assign(N + 1, 0);
	for (int i = 1; i <= N; i++)
		cin >> T[i];
	sort(T.begin() + 1, T.end());
	for (int i = 1; i <= N; i++)
		Sum[i] = Sum[i - 1] + T[i];
	que.push_back({0, 0});
	for (int i = 1; i <= N; i++) {
		while (add.empty() == 0 && T[i] - T[add.front().position] >= M) {
			while (que.empty() == 0 && JudgeBack(add.front()))
				que.pop_back();
			que.push_back(add.front());
			add.pop();
		}
		while (q.empty() == 0 && (JudgeFront_Q(i) || T[i] - T[q.front().position] >= M))
			q.pop_front();
		while (que.empty() == 0 && JudgeFront(T[i]))
			que.pop_front();
		DP[i] = que.front().F - Sum[i] + (i - que.front().position) * T[i];
		if (!q.empty()) {
			DP[i] = min(DP[i], q.front().F + i * (T[q.front().position] + M) - Sum[i]);
		}
		if(i==N)	break;
		while (q.empty() == 0 && JudgeBack_Q({DP[i] - i*T[i] + Sum[i] + i * M, i, -T[i]}))
			q.pop_back();
		q.push_back({DP[i] - i*T[i] + Sum[i] - i * M, i, -T[i]});
		add.push({DP[i] + Sum[i], i});
	}
	cout << DP[N];
	return 0;
}

测试记录

推出来的

$M \le T_i-T_{j/k}$时$\frac{DP_k+S_k-DP_j-S_j}{k-j} <T_i$

$T_i-T_{j/k}<M$时$\frac{DP_k-kT_k+S_k-km-(DP_j-jT_j+S_j-jm)}{-T_k-(-Tj)}<i$