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;
}
更多推荐
1468H
发布评论