New Game--（单调队列）

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

Inputcopy	Outputcopy
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 1	6 3 9 2

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int n, k, t,max0=0;
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 (r==l) {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 h=hebing();max.max = 0;max.g = 0;for (int i = 0;i < h;i++) {if (max.g < k ) {//不相同的数小于k个if(max.g==0){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;
}