首先判掉 \((n-m)\bmod (k-1)\ne0\) 的情况,显然是无解的。
考虑消去的最后一步,必然是以 \(b\) 中的某一元素为中位数进行的。
于是得到了一个必要条件:存在一个 \(b_i\),满足 \(a\) 中 \(b_i\) 的两侧都至少有 \(\frac{k}{2}\) 个不在 \(b\) 中的数。
构造说明这也是充分条件。
启发:可以考虑从最后一步入手,大胆猜想,小心求证。
Code:
#include <bits/stdc++.h>
using namespace std;
#define YES return printf("YES\n"), void()
#define NO return printf("NO\n"), void()
const int N = 200005;
int T;
int n, k, m;
int a[N];
void solve() {
scanf("%d%d%d", &n, &k, &m);
for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
if ((n - m) % (k - 1)) NO;
for (int i = 1; i <= m; ++i)
if (a[i] - i >= (k - 1) / 2 && n - a[i] - (m - i) >= (k - 1) / 2) YES;
NO;
}
int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}
标签:CF1468H,return,NO,int,void,d%,YES
From: https://www.cnblogs.com/Kobe303/p/16800951.html