个人可否建立网站,陕西旭泽建设有限公司网站,网站设计教程视频下载,国际物流公司网站建设I - New Game
有一种新的游戏#xff0c;Monocarp 想要玩。这个游戏使用一副包含 n 张牌的牌堆#xff0c;其中第 i 张牌上写有一个整数 a_i。
在游戏开始时#xff0c;Monocarp 可以在第一轮选择牌堆中的任意一张牌。在接下来的每一轮中#xff0c;Monocarp 可以选择一张…I - New Game
有一种新的游戏Monocarp 想要玩。这个游戏使用一副包含 n 张牌的牌堆其中第 i 张牌上写有一个整数 a_i。
在游戏开始时Monocarp 可以在第一轮选择牌堆中的任意一张牌。在接下来的每一轮中Monocarp 可以选择一张牌这张牌上的数字必须与上一轮选择的牌上的数字相同或者比上一轮选择的牌上的数字大 1。
换句话说如果 Monocarp 在上一轮选择了一张数字为 x 的牌那么在当前轮他可以选择一张数字为 x 或 x 1 的牌。 Monocarp 可以选择任何符合条件的牌无论它在牌堆中的位置如何。
在 Monocarp 选择了一张牌后这张牌会从牌堆中移除。
根据游戏规则Monocarp 所选择的牌上的不同数字的数量不能超过 k。
如果在某一轮后Monocarp 无法在不违反上述规则的情况下选择一张牌游戏结束。
你的任务是确定 Monocarp 在游戏过程中可以从牌堆中拿取的最大牌数假设他在第一轮可以选择任意一张牌。 输入 第一行包含一个整数 t(1 ≤ t ≤ 10 ^ 4) —— 测试用例的数量。 每个测试用例的第一行包含两个整数 n 和 k(1 ≤ k ≤ n ≤ 200, 000) —— 牌堆中的牌数和 Monocarp 可以选择的牌上不同数字的最大数量。 第二行包含一个整数序列 a_1, a_2, ..., a_n(1 ≤ a_i ≤ 10 ^ 9)其中 a_i 是第 i 张牌上的数字。 输入的额外约束所有测试用例的 n 之和不超过 200, 000。 输出 对于每个测试用例输出 Monocarp 在游戏过程中可以从牌堆中拿取的最大牌数 假设他在第一轮可以选择任意一张牌。
Examples
InputcopyOutputcopy 4
10 2
5 2 4 3 4 3 4 5 3 2
5 1
10 11 10 11 10
9 3
4 5 4 4 6 5 4 4 6
3 2
1 3 16
3
9
2 代码
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
int n, k, t,max00;
int a[200000], b[200000];
struct s {int x;//值int sum;//个数
}c[200000];//记录从小到大排好序列的值和个数
struct ss {int max;int g 0;
}max;//k个数内的和和个数
//归并排序
void guibing(int l, int r) {if (rl) {return ;}int mid l (r - l) / 2;guibing(l, mid);guibing(mid 1, r);int l_1 l, r_1 mid 1, ll l;while (l_1 mid r_1 r) {if (a[l_1] a[r_1]) {b[ll] a[r_1];}else {b[ll] a[l_1];}}while (l_1 mid) {b[ll] a[l_1];}while (r_1 r) {b[ll] a[r_1];}for (int i l;i r;i) {a[i] b[i];}
}
//合并相同的数并记录个数
int hebing() {int j 0;c[j].sum 1;c[j].x a[0];j;for (int i 1;i n;i) {if (c[j - 1].x a[i]) {c[j - 1].sum;}//相同else {c[j].sum 1;c[j].x a[i];j;}//不相同}return j;//返回有多少给不相同的数
}
int main() {scanf(%d, t);while (t--) {max0 0;scanf(%d %d, n, k); for (int i 0;i n;i) {scanf(%d, a[i]);c[i].sum 0;c[i].x 0;}guibing(0, n - 1);int hhebing();max.max 0;max.g 0;for (int i 0;i h;i) {if (max.g k ) {//不相同的数小于k个if(max.g0){max.max c[i].sum;max0 max.max max0 ? max.max : max0;max.g 1;}else if (c[i].x c[i - 1].x 1) {max.max c[i].sum;max0 max.max max0 ? max.max : max0;max.g;}else {//相邻的数只能差0/1max.g 1;max.max c[i].sum;max0 max.max max0 ? max.max : max0;}}else{//等于k个if(c[i].x c[i - 1].x 1){max.max c[i].sum - c[i - k].sum;max0 max.max max0 ? max.max : max0;}else {//相邻的数只能差0/1max.g 1;max.max c[i].sum;max0 max.max max0 ? max.max : max0;}}}printf(%d\n, max0);}return 0;
}
