题解

题面描述

设计一种消消乐的算法，使用数字代表不同类型的格子。拥有一种道具，可以对某个格子进行加一或减一的变化。给定一个整数数组 nums 表示当前的格子状态，以及一个整数 k 表示道具的数量。最多可以使用 k 个道具，最终返回同类型格子最多的个数作为最终得分。

思路

通过排序数组并应用滑动窗口技术，选择一个目标值（通常为中位数），计算将窗口内所有数字调整到该目标值所需的操作次数，确保总操作不超过k次。使用前缀和和双指针方法优化计算过程，逐步扩大窗口以找到包含最多相同元素的最大子集，从而实现高效且准确的优化目标。

具体步骤如下：

1. 排序：首先对数组 nums 进行排序，这样相同或接近的数字会聚集在一起，便于计算操作次数。

2. 前缀和：计算数组的前缀和，以便快速计算任意区间内数字的总和。

3. 滑动窗口：使用滑动窗口的方法，维护一个窗口 [left, right]，窗口内的数字通过操作可以全部变为窗口内的中位数。计算将窗口内所有数字变为中位数所需的操作次数，如果超过 k，则缩小窗口左边界。

4. 更新结果：在遍历过程中，不断更新最大的窗口大小，即为最终结果。

cpp

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    vector<ll> nums;
    ll num;
    
    // 读取第一行的 nums 数组
    string line1;
    getline(cin, line1);
    stringstream ss1(line1);
    while(ss1 >> num){
        nums.push_back(num);
    }
    
    // 读取第二行的 k
    string line2;
    getline(cin, line2);
    ll k = 0;
    if(!line2.empty()){
        stringstream ss2(line2);
        ss2 >> k;
    }
    
    // 排序
    sort(nums.begin(), nums.end());
    
    int n = nums.size();
    // 计算前缀和
    vector<ll> prefix_sum(n +1, 0);
    for(int i=0;i<n;i++) prefix_sum[i+1] = prefix_sum[i] + nums[i];
    
    ll max_len =1;
    int left =0;
    for(int right=0; right<n; right++){
        // 计算当前窗口 [left, right] 的中位数
        int mid = left + (right - left) /2;
        ll m = nums[mid];
        
        // 计算左半部分的操作次数
        ll sum_left = m * (mid - left) - (prefix_sum[mid] - prefix_sum[left]);
        
        // 计算右半部分的操作次数
        ll sum_right = (prefix_sum[right+1] - prefix_sum[mid+1]) - m * (right - mid);
        
        // 总操作次数
        ll total = sum_left + sum_right;
        
        // 如果操作次数超过 k，移动左指针
        while(total >k){
            left++;
            if(left > mid){
                mid = left + (right - left) /2;
                m = nums[mid];
            }
            else{
                mid = left + (right - left) /2;
                m = nums[mid];
            }
            sum_left = m * (mid - left) - (prefix_sum[mid] - prefix_sum[left]);
            sum_right = (prefix_sum[right+1] - prefix_sum[mid+1]) - m * (right - mid);
            total = sum_left + sum_right;
        }
        // 更新最大长度
        max_len = max(max_len, (ll)(right - left +1));
    }
    
    cout << max_len;
}

python

import sys

def main():
    import sys
    nums = []
    
    # 读取第一行的 nums 数组
    line1 = sys.stdin.readline()
    nums = list(map(int, line1.strip().split()))
    
    # 读取第二行的 k
    line2 = sys.stdin.readline()
    if line2:
        k = int(line2.strip())
    else:
        k =0
    
    nums.sort()
    n = len(nums)
    prefix_sum = [0]*(n+1)
    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + nums[i]
    max_len =1
    left=0
    for right in range(n):
        # 计算当前窗口 [left, right] 的中位数
        mid = left + (right - left) //2
        m = nums[mid]
        # 计算左半部分的操作次数
        sum_left = m * (mid - left) - (prefix_sum[mid] - prefix_sum[left])
        # 计算右半部分的操作次数
        sum_right = (prefix_sum[right+1] - prefix_sum[mid+1]) - m * (right - mid)
        # 总操作次数
        total = sum_left + sum_right
        # 如果操作次数超过 k，移动左指针
        while total >k:
            left +=1
            if left > mid:
                mid = left + (right - left) //2
                m = nums[mid]
            else:
                mid = left + (right - left) //2
                m = nums[mid]
            sum_left = m * (mid - left) - (prefix_sum[mid] - prefix_sum[left])
            sum_right = (prefix_sum[right+1] - prefix_sum[mid+1]) - m * (right - mid)
            total = sum_left + sum_right
        # 更新最大长度
        max_len = max(max_len, right - left +1)
    print(max_len)

if __name__ == "__main__":
    main()

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));
        
        // 读取第一行的 nums 数组
        String line1 = br.readLine();
        String[] parts1 = line1.trim().split("\\s+");
        ArrayList<Long> numsList = new ArrayList<>();
        for(String s : parts1){
            if(!s.isEmpty()){
                numsList.add(Long.parseLong(s));
            }
        }
        
        // 读取第二行的 k
        String line2 = br.readLine();
        long k =0;
        if(line2 != null && !line2.trim().isEmpty()){
            k = Long.parseLong(line2.trim());
        }
        
        // 将 nums 转为数组并排序
        int n = numsList.size();
        long[] nums = new long[n];
        for(int j=0; j<n; j++) nums[j] = numsList.get(j);
        Arrays.sort(nums);
        
        // 计算前缀和
        long[] prefix_sum = new long[n+1];
        for(int j=0; j<n; j++) prefix_sum[j+1] = prefix_sum[j] + nums[j];
        
        long max_len =1;
        int left=0;
        for(int right=0; right<n; right++){
            // 计算当前窗口 [left, right] 的中位数
            int mid = left + (right - left) /2;
            long m = nums[mid];
            // 计算左半部分的操作次数
            long sum_left = m * (mid - left) - (prefix_sum[mid] - prefix_sum[left]);
            // 计算右半部分的操作次数
            long sum_right = (prefix_sum[right+1] - prefix_sum[mid+1]) - m * (right - mid);
            // 总操作次数
            long total = sum_left + sum_right;
            // 如果操作次数超过 k，移动左指针
            while(total >k){
                left++;
                if(left > mid){
                    mid = left + (right - left) /2;
                    m = nums[mid];
                }
                else{
                    mid = left + (right - left) /2;
                    m = nums[mid];
                }
                sum_left = m * (mid - left) - (prefix_sum[mid] - prefix_sum[left]);
                sum_right = (prefix_sum[right+1] - prefix_sum[mid+1]) - m * (right - mid);
                total = sum_left + sum_right;
            }
            // 更新最大长度
            max_len = Math.max(max_len, (long)(right - left +1));
        }
        System.out.println(max_len);
    }
}

题目内容

现在要设计一种消消乐的算法，我们用数字代表一种类型格子，有一种道且可以对某个格子进行加一或者减一的变化。 现在给你一个整数数组$nums$代表当前的格子状态和一个整数$k$代表道具数量。你最多可以使用$k$个道具，最终返回同类型格子最多的个数作为你的最终得分

输入描述

一个整数数组$nums$代表当前的格子状态

一个整数$k$代表道具数量

$1 <= nums.length <=10^5$

$1 <= nums[i]<=10^9$

$0 <= k <= 10^9$

输出描述

使用道具后同类型格子最多的个数

样例1

输入

1 2 6 4
3

输出

3

说明

有$1，2，6，4$四种格子

有$3$个道具可以使用

使用后最多可以有$3$个相同格子$(2，2，6，2)$

样例2

输入

1 2 3 4
0

输出

1

说明

有$1，2，3，4$四种格子

有$0$个道具可以使用

使用后最多可以有$1$个相同格子 $(1，2，3，4)$