1468H

1468H

1468H - K and Medians（思维）

传送门

题意

给定一个长 n n n 的数组 a a a ，要求你每次选择可以不连续的 k k k 个点（ k k k 保证是奇数），删除除了这 k k k 个点的中位数以外的所有数。问能否通过一定次数（可以为0）的操作，得到长度为 m m m 的数组 b b b ？

思路

参考：[CF1468H] K and Medians - 思维

• 第一，每次一定是删除 k − 1 k - 1 k−1 个数字，所以最后删除的元素总数是 x ∗ ( k − 1 ) x * (k - 1) x∗(k−1) 个（消除 x x x 次），也就意味着必须有 ( n − m ) % ( k − 1 ) = 0 (n - m) \% (k - 1) = 0 (n−m)%(k−1)=0 。
• 第二，我们怎么去安排这 n − m n - m n−m 次消除？由答案倒推可得，最后一次消除一定是以其中一个数为中位数，消除左边的 ( k − 1 ) / 2 (k - 1) / 2 (k−1)/2 个和右边的 ( k − 1 ) / 2 (k - 1) / 2 (k−1)/2 个。由此最后一次消除的中位数一定满足：a. 在最终需要的串中出现，b. 在最开始的时候左右各有不少于 k / 2 k / 2 k/2 个数待消除。
• 那么之前的 x − 1 x - 1 x−1 次怎么安排呢？我思考了很久才明白过来其实不用管这这个。只要有一个满足第二点的中位数，就总有办法消除到满足条件的最后一步。

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pb push_back
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int N = 3e5 + 19;
const ll mod = 1e9 + 7;int a[N];
int n, m, k;bool ok()
{if((n - m) % (k - 1))return 0;for(int i = 0; i < m; i++){if((a[i] - i - 1) >= (k / 2) && n - m - (a[i] - i - 1) >= k / 2)return 1;}return 0;
}int main()
{int T;cin >> T;while(T--){cin >> n >> k >> m;for(int i = 0; i < m; i++){cin >> a[i];}if(ok())cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}