Educational Codeforces Round 170 C New Game

思路

滑动窗口

排完序后找左右边界差值小于等于k 的最长子序列长度即可

可以用map去重

代码

#include <bits/stdc++.h>
using namespace std;const int N = 200010;int t, n, k;
int a[N], b[N];void solve()
{cin >> n >> k;for (int i = 1; i <= n; i ++ ) cin >> a[i];map<int, int> ump;int tt = 0;for (int i = 1; i <= n; i ++ ){if (!ump[a[i]]){b[tt ++ ] = a[i];}ump[a[i]] ++;}sort(b, b + tt);int res = 0;int i, j;int temp = 0;for (i = 0, j = 0; i < tt; i ++ ){j = max(i, j);if (j == i)temp = ump[b[i]];elsetemp -= ump[b[i - 1]];while (j < tt - 1 && b[j] + 1 == b[j + 1] && j - i + 1 < k){j ++;temp += ump[b[j]];}res = max(res, temp);}cout << res << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> t;while (t -- ){solve();}
}