题解 | #C 夜揽星河入梦#

~~第一次发题解，请多包涵~~

由于题目保证给出的数据是不存在 $m$ 个坐标直接满足题意，因此题目要求我们找到 $m - 1$ 个棋子的坐标，从小到大排列之后再插入一个棋子，能使原先这些棋子的坐标构成一个公差为 1 的等差数列。

那么我们在在读入数据之后可以先对这些数据进行从小到大的排序。而由于公差为 1 ，所以我们找到的最终满足条件的坐标一定在原数组中是连续的，即最终满足题意的 $m - 1$ 个棋子的坐标一定是原数组的一个子数组。

我们可以认为，满足题意的的一个子数组是由一个满足题意的等差数列去除其中任意一个数生成的。这就要引出一个重要性质：若一个有限长度等差数列的长度为 $m$ ，则其最后一个元素与第一个元素之差一定为 $m - 1$ ，即 $a_m - a_1 = m - 1$ 。而根据去除的数的位置可以被分为两种情况：

去掉的元素是原本不在首尾的元素，那么这个等差数列的长度减一，但首尾差不变，即 $a_{m-1} - a_1 = m - 1$ 。
去掉的元素是第一个元素或最后一个元素，那么这个等差数列的长度减一，首尾差也减一，即 $a_{m-1} - a_1 = m - 2$ 。

反过来，只要我们找到给出的数据（从小到大排序后）中存在任意一段长度为 $m - 1$ 的子数组满足如上两种情况其一的结论即可说明，我们能找到满足题意的子数组，使得再添一个坐标能使该子数组成为公差为 1 的等差数列。

代码如下

#include <iostream>
#include <algorithm>
using namespace std;

constexpr int N = 2e5 + 10;
int T, n, m, arr[N];

void solve()
{
    cin >> n >> m;
    for (int i=1; i<=n; i++)
        cin >> arr[i];
    sort(arr + 1, arr + n + 1);
    bool flag = false;
    for (int i=1; i<=n-m+2; i++)
    {
        if (arr[i+m-2] - arr[i] == m - 1 || arr[i+m-2] - arr[i] == m - 2)
        {
            flag = true;
            break;
        }
    }
    if (flag)
        cout << "YES\n";
    else
        cout << "NO\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> T;
    while (T--)
        solve();
    return 0;
}

时间复杂度为 $O(TN)$ 。