leetcode

0 static const auto _ = [] {

1 cin.tie(0);

2 ios::sync_with_stdio(0);

3 return 0;

4 }();

5 class Solution {

6 public:

7 int maxFrequency(vector<int> &nums, int k) const {

8 static long long prefix[100001];

9 const int n = nums.size();

10

11 memset(prefix, 0x00, sizeof(prefix));

12 for (int i = 0; i < n; i++)

13 prefix[nums[i]]++;

14

15 for (int i = 0, j = 0; i <= 100000; i++) {

16 while (prefix[i] > 0) {

17 nums[j++] = i, prefix[i]--;

18 }

19 }

20

21 prefix[0] = 0;

22 for (int i = 1; i < n; i++)

23 prefix[i] = nums[i - 1] + prefix[i - 1];

24

25 int res = 0;

26 for (int crnt = 0; crnt < n; crnt++) {

27 int low = 0, high = crnt - 1;

28 while (low <= high) {

29 const int mid = low + (high - low) / 2;

30 const long long left = crnt - mid;

31 const long long sum = prefix[crnt] - prefix[mid];

32 if (left * nums[crnt] - sum <= k)

33 high = mid - 1;

34 else

35 low = mid + 1;

36 }

37 res = max(res, crnt - high);

38 }

39

40 return res;

41 }

42 };