思路
注意：所有变量名与原题面相同。
因为 \(1\) 号点必须吃一块饼干，所以我们可以在 \(1\) 立一个不可删除的商店，记为 \(s_0\)。
注意：如果 \(1\) 号附近本身就有一个商店，那就不用立。
然后我们可以在 \(n + 1\) 的位置立一个不可删除的商店，作为一个结束标志，记为 \(s_{m + 1}\)。
然后我们可以进行分段分为 \(m + 1\) 段，即 \([s_0,s_1),[s_1, s_2),[s_2, s_3),\dots,[s_{m - 1},s_m),[s_m, s_{m + 1})\)，注意是左闭右开区间。
对于区间 \([l, r)\)，我们要吃多少饼干呢？画一画就可以知道要吃 \({\left\lceil\frac{r - l}{d}\right\rceil}\) 。
利用这个公式，我们可以求出不删除商店要吃饼干的数量 \(\text{init}\)，就是把每一段吃的饼干加起来。
即计算 \(\text{init} = \sum\limits_{i = [s_1 = 1]}^{m}\left\lceil\frac{s_{i + 1} - s_i}{d}\right\rceil\)。
实际上，如果要删掉 \(x\) 商店，
那么只要拿最初的 \(\text{init}\) 删除 \([s_{x - 1}, s_x)\) 和 \([s_x, s_{x + 1})\) 吃的饼干，这是在清除原有数据。
再加上 \([s_{x - 1}, s_{x - 1, x + 1})\) ，这是在计算删除商店后这一段会吃掉的饼干。
即 \(ans = \text{init} - \left\lceil\frac{s_x - s_{x - 1}}{d}\right\rceil - \left\lceil\frac{s_{x + 1} - s_x}{d}\right\rceil + \left\lceil\frac{s_{x + 1} - s_{x - 1}}{d}\right\rceil\)，就是删掉 \(x\) 商店要吃的饼干了。
最后我们求出所有 \(ans\) 的最小值并统计一下数量 \(cnt\) 就可以了。
同时，我们要注意，如果 \(1\) 号点附近本身就有一个商店，那么删掉该商店以后，答案还是 \(\text{init}\)，也要参与统计。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;
int n, m, d;
int s[N];
inline int cnt(int l, int r) {
int sz = r - l;
if (sz % d == 0) return sz / d;
return sz / d + 1;
}
void solve() {
cin >> n >> m >> d;
for (int i = 1; i <= m; i++) cin >> s[i];
bool flag = true;
if (s[1] != 1) {
flag = false;
m++;
for (int i = m; i >= 2; i--) s[i] = s[i - 1];
s[1] = 1;
}
m++;
s[m] = n + 1;
int init = 0;
for (int i = 2; i <= m; i++) init += cnt(s[i - 1], s[i]);
int minn = 0x3f3f3f3f3f3f3f3f, ans = 0;
for (int i = 2; i < m; i++) {
int g = init - cnt(s[i - 1], s[i]) - cnt(s[i], s[i + 1]) + cnt(s[i - 1], s[i + 1]);
if (g < minn) {
minn = g;
ans = 1;
}
else if (g == minn) ans++;
}
if (init < minn && flag) minn = init, ans = 1;
else if (init == minn && flag) minn = init, ans++;
cout << minn << ' ' << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}