CF1858B

题面

Link

题目大意：

Petya 在沿着长椅散步，一共有 $n$ 个长椅，有 $m$ 个卖饼干的人分别在一个长椅旁。

Petya 本身有一堆饼干，它吃饼干有一个 CD，一旦 CD 过了它就会吃饼干，如果它还没有吃任何饼干那么它也会吃饼干（第一个长椅），假如遇到了一个长椅旁有卖饼干的，它也会吃一个饼干，注意每次吃完饼干会重置吃饼干的 CD。

现在会去掉一个卖饼干的，问让 Petya 吃到最少的饼干数是多少？有多少种方案？

思路

首先我们假设不去掉一个卖饼干的，Petya 一共可以吃多少饼干。

相邻两个卖饼干的人组成了一个区间的左右端点，我们先考虑求一个区间内它能吃多少饼干，经过一番演算得到了这样的式子：$\lfloor\frac{s_i-s_{i-1}-1}{d}\rfloor$

它表示这段区间内不含左右端点所能吃到的饼干总数，也就是一个开区间。

为了方便累加，我们记为左开右闭区间，即 $\lfloor\frac{s_i-s_{i-1}-1}{d}\rfloor+1$ ，为了算上开头和结尾的两段区间，我们再加上两个端点 $1-d,n+1$，$1-d$ 可以刚好使得 1 号长椅处 Petya 吃一个饼干，而 $n+1$ 作为最后一个区间的右端点刚好可以覆盖最后的区间，由于 $n+1$ 这个右端点实际不存在，所以最后一个区间是左开右开区间，也就是累加完后再把多算的一个减去即可。

然后考虑分别去掉每一个卖饼干的人会造成怎样的影响。

假如去除掉了位置为 $s_i$ 的卖饼干的人，那么 $(s_{i-1}, s_i)$ 和 $(s_i,s_{i+1})$ 的贡献将被减掉，同时减掉在 $s_i$ 处吃掉的饼干，再加上 $(s_{i-1},s_{i+1})$ 的贡献，即：

$\Delta = \lfloor\frac{s_{i+1}-s_{i-1}-1}{d}\rfloor - \lfloor\frac{s_i-s{i-1}-1}{d}\rfloor - \lfloor\frac{s_{i+1}-s_i-1}{d}\rfloor$

那么我们枚举一遍，维护一下答案的最小值是多少，假如相等了就把方案加一即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;

vector<int> s;

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, m, d;
        s.clear();
        scanf("%d%d%d", &n, &m, &d);
        for(int i = 1; i <= m; i++)
        {
            int t;
            scanf("%d", &t);
            s.push_back(t);
        }
        s.insert(s.begin(), 1 - d);
        s.push_back(n + 1);
        sort(s.begin(), s.end());
        int ans = 0x3f3f3f3f;
        int lenth = 0;
        int res = 0;
        for(int i = 1; i <= m + 1; i++) // m + 2 元素
        {
            res += (s[i] - s[i - 1] - 1) / d + 1;
        }
        res--;
        for(int i = 1; i <= m; i++) // m 元素
        {
            int tmp = res + (s[i + 1] - s[i - 1] - 1) / d - (s[i] - s[i - 1] - 1) / d - (s[i + 1] - s[i] - 1) / d - 1;
            if(tmp < ans)
            {
                ans = tmp;
                lenth = 1;
            }
            else if(tmp == ans)
            {
                lenth++;
            }
        }
        cout << ans << ' ' << lenth << endl;
    }
    return 0;
}