![]()
#include <stdio.h> #include <stdlib.h> #define MAX_N 100000 int a[MAX_N]; // 存储输入的数组 long long prefix[MAX_N+1];// 前缀和数组 int cmp(const void* x, const void* y) { return *(int*)x - *(int*)y; } int main() { int T; scanf("%d", &T); // T表示有多少组测试数据 while (T--) { int n; // 数组长度（改为局部变量） long long k; // 最多操作次数 scanf("%d %lld", &n, &k); // 读取数组元素 for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } // 数组排序：升序排序是滑动窗口的前提！！！ qsort(a, n, sizeof(int), cmp); // 构建前缀和数组 prefix[0] = 0; for (int i = 0; i < n; i++) { prefix[i + 1] = prefix[i] + a[i]; } // 滑动窗口核心逻辑：找最大窗口（最多k次操作能让窗口内元素全相同） int left = 0; // 窗口左指针，初始为0 int max_cnt = 1; // 最大众数次数，至少有1个元素 for (int right = 0; right < n; right++) { // right是窗口右指针，遍历每个元素作为目标值 /** * 关键公式：计算将[left, right]区间内所有元素变为a[right]所需的操作次数 * 操作次数 = 目标值*窗口长度 - 区间内元素和 * a[right]*(right-left+1)：窗口内所有元素都变成a[right]的总和 * prefix[right+1]-prefix[left]：窗口内当前元素的总和 * 两者的差值就是需要增加的次数 */ while ((long long)a[right] * (right - left + 1) - (prefix[right + 1] - prefix[left]) > k) { left++; // 操作次数超过k，左指针右移，缩小窗口 } // 更新最大窗口长度（即最大众数次数） if ((right - left + 1) > max_cnt) { max_cnt = right - left + 1; } } printf("%d\n", max_cnt); } return 0; }
