小红的高频数字

题目链接: https://www.nowcoder.com/practice/b985c93a6fc949128682b4134aa2ebf7

题意

给定长度为 $n$ 的数组和最多 $k$ 次操作，每次操作可以将某个数加一。问操作后数组中出现次数最多的数最多出现几次。

解题思路

排序 + 滑动窗口

核心观察：

最优策略一定是选取一段连续区间的数，把它们都变成同一个数（即区间最大值）。
若数组排序后，选区间 $[l, r]$ ，把所有数都变成 $a[r]$ ，所需操作数为 $a[r] \times (r - l + 1) - \sum_{i=l}^{r} a[i]$ 。

算法：

对数组排序。
使用滑动窗口维护区间 $[l, r]$ ，同时维护区间和 $sum$ 。
固定右端点 $r$ ，若当前窗口的操作数超过 $k$ ，则移动左端点 $l$ 直到满足条件。
更新答案为窗口大小 $r - l + 1$ 的最大值。

复杂度： $O(n \log n)$ （排序主导）

示例验证

示例1：[1, 3, 4, 5, 9]， $k=4$

排序后：[1, 3, 4, 5, 9]
当 $r=3$ （ $a[r]=5$ ）：

- 窗口 $[1,3]$ （即 $[3,4,5]$ ），操作数 $= 5 \times 3 - 12 = 3 \le 4$ ，窗口大小 3

答案为 3 ✓

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, k;
    cin >> n >> k;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());

    long long ans = 1;
    long long l = 0;
    long long sum = 0;

    for (long long r = 0; r < n; r++) {
        sum += a[r];
        // cost = a[r] * (r - l + 1) - sum
        while (a[r] * (r - l + 1) - sum > k) {
            sum -= a[l];
            l++;
        }
        ans = max(ans, r - l + 1);
    }

    cout << ans << endl;

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());

        long[] a = new long[(int)n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(a);

        long ans = 1;
        long l = 0;
        long sum = 0;

        for (long r = 0; r < n; r++) {
            sum += a[(int)r];
            while (a[(int)r] * (r - l + 1) - sum > k) {
                sum -= a[(int)l];
                l++;
            }
            ans = Math.max(ans, r - l + 1);
        }

        System.out.println(ans);
    }
}

关键点

只能加不能减，所以最优目标值一定是窗口内的最大值（即右端点）。
数据范围可能较大，注意使用 long long 避免溢出（尤其是 $a[r] \times (r-l+1)$ 这一乘积）。
滑动窗口左右端点合法性：窗口始终满足操作数 $\le k$ 。