NC224938 加减

枚举 二分 前缀和

给定可以改变的次数k，要求改变后出现次数最多的数，那么一定是由该数“附近”元素构成的一段连续子序列花完k次变化后得到。或者可以说，k是这一段连续子序列到目标值的距离之和。

所以主要的解题思路：

• 原数组排序，求前缀和
• 枚举左端点L
• 二分右端点R
• 目标数一定是L和R区间内的中位数（数学规律，试想目标值偏小或偏大都会导致距离和变大）
• 前缀和求出 [ L ,R ] 区间元素到中位数的距离之和，与k比较

AC代码：

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

typedef long long int ll;

ll n, k;
ll a[100005];       // 原数组
ll preSum[100005];  // 前缀和 prefix Sum
int ans;

ll cal(int L,int R){
    int mid = (L + R) / 2;
    //前缀和求距离和
    return preSum[R] - preSum[mid] - preSum[mid - 1] + preSum[L - 1] - a[mid] * (R - mid) + a[mid] * (mid - L);
}

int main(){
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1);         // 排序
    for (int i = 1; i <= n; i++)    // 求前缀和
        preSum[i] = preSum[i - 1] + a[i];
    for (int i = 1; i <= n; i++){   // 枚举区间左端点
        int l = i, r = n; 
        while(l<=r){                // 二分右端点
            int mid = (l + r) / 2;
            if(cal(i,mid)<=k)
                l = mid + 1, ans = max(ans, mid - i + 1);
            else
                r = mid - 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}