B. The Walkway Codeforces Round 893 (Div. 2)

Problem - B - Codeforces

题目大意：小明在数轴上要从1走到n，其中某些坐标上有一些饼干店，共m个，小明身上也有无限多的饼干，它首先一定会在1的位置吃一个饼干，在每个饼干店的位置会吃一个，在前d个位置没有吃饼干（加入当前位置为i，在[i-d+1，i]之间没有吃饼干），就会吃一个，以上三种情况如果有某些同时发生，只会吃一个，现在要求移除一个商店，问小明吃的最少的饼干数是多少，且满足这个饼干数的方案有多少种

2<=n<=1e9；2<=m<=min(1e5,n)

思路：要知道移除哪些商店最好，只能是枚举每个商店，维护移除该商店前和移除后的饼干数，移除前的饼干数，直接用原始的数组求，我们在位置1的位置吃一个，然后对于第一个商店，产生的贡献就是(a[i]-1)/d，向上取整，对于后面的每个商店，因为前一个商店已经算过了，所以产生的贡献就是(a[i]-a[i-1])/d，向上取整，这样就算出了初始不移除商店的饼干数

接下来枚举每个商店，先用总贡献减去这个商店的贡献，先减去自身的1，然后减去前一部分也就是(a[i]-a[i-1]/d)，因为不能重复减去这个商店的贡献，所以如果是整除的话，要再+1，然后减去后一部分(a[i+1]-a[i])/d，因为不能减去右边商店的贡献，所以如果整除也要+1。然后再加上移除这个商店后，i-1和i+1之间的贡献，也就是(a[i+1]-a[i-1])/d，同理因为不能算边界，所以如果整除要-1。

之后就得到了每个商店移除前后的饼干数，维护最小值并统计最小值数量即可

#include<bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int INF = 0x7fffffff;
const ll MOD = 998244353;
int n;
ll a[N];
void init()
{}
void solve()
{cin >> n;init();ll m, d;cin >> m >> d;a[m + 1] = n;//方便处理边界for (int i = 1; i <= m; i++){      cin >> a[i];}ll cnt = 0;for (int i = 1; i <= m; i++){if (i == 1 && a[i] != 1)cnt++;//先处理位置1，之后就不用管左边界了cnt += (a[i] - a[i - 1] - 1) / d + 1;//记录原始数组的总饼干数}if(a[m]!=n)cnt += (n - a[m]) / d;//特判n的位置有没有处理过ll micnt = cnt;ll cntans = 0;for (int i = 1; i < m; i++){ll temp = cnt - 1;//移除这个商店后的饼干数temp -= (a[i] - a[i - 1]) / d;//先减去这个歌商店原来的贡献if ((a[i] - a[i - 1]) % d == 0){temp++;}temp -= (a[i+1] - a[i]) / d;if ((a[i+1] - a[i]) % d == 0){temp++;}temp += (a[i + 1] - a[i - 1]) / d;//加上这个区间新的贡献if ((a[i + 1] - a[i - 1]) % d == 0){temp--;}if (temp < micnt){micnt = temp;//维护最小值cntans = 1;//维护最小值数量}else if (temp == micnt){cntans ++ ;}}ll temp = cnt - 1;temp -= (a[m] - a[m - 1]) / d;//因为最后一个商店没有右边的商店，所以单独处理一下if ((a[m] - a[m - 1]) % d == 0){temp++;}temp -= (a[m + 1] - a[m]) / d;temp += (a[m + 1] - a[m - 1]) / d;if (temp < micnt){micnt = temp;cntans = 1;}else if (temp == micnt){cntans++;}   cout << micnt << " " << cntans << endl;
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int t;cin >> t;a[0] = 1;while (t--){solve();}return 0;
}