[NC224938] 加减

题目

题目描述

小红拿到了一个长度为 $n$ 的数组。她每次操作可以让某个数加 $1$ 或者某个数减 $1$ 。
小红最多能进行 $k$ 次操作。她希望操作结束后，该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗？

输入描述

第一行两个正整数 $n$ 和 $k$
第二行有 $n$ 个正整数 $a_i$

$1≤n≤10^5$
$1≤k≤10^{12}$
$1≤a_i≤10^9$

输出描述

不超过 $k$ 次操作之后，数组中可能出现最多次数元素的次数。

示例1

输入

1
2
5 3
6 3 20 8 1

输出

1
2

说明

共 $3$ 次操作如下：
第一个数加一。
第二个数加一。
第四个数减一。
数组变成了 $7,4,20,7,1$ ，共有 $2$ 个相同的数：$7$ 。
可以证明，$2$ 为最优解。另外，此上操作并不是唯一的操作。

题解

知识点：二分，前缀和，双指针，枚举。

排序好数列中，若要构成相同的数字，那么构成子串是同样情况下花费次数最少的，因此考虑遍历所有左端点，且每次左移左端点不需要回调右端点，因为左移端点后区间长度一定小于等于原来合法最大值，就算区间内有合法右端点但也不可能更新最大值，所以不考虑回调。(尺取法)

在同一个区间所有数字离中位数最近，消耗次数最小，偶数区间中间两个数字选取等价。(二分)

为了方便计算某区间的消耗，需要预处理出排序好后的前缀和。（前缀和）

时间复杂度 $O(n\text {log}n)$

空间复杂度 $O(n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <algorithm>
#define LL long long

using namespace std;
const int MAX = 1e5+10;

LL a[MAX],s[MAX];

int main(){
    std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    LL n,k;
    cin>>n>>k;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i = 1;i<=n;i++){
        s[i] = s[i-1] + a[i];
    }
    int l = 1,r = 1;
    int ans = 0;
    while(l<=n){
        while(r<=n){
            int mid = l+r>>1;//中间值;
            if((mid-l)*a[mid]-(s[mid-1]-s[l-1]) + (s[r]-s[mid]) - (r-mid)*a[mid]>k) break;
            r++;
        }
        ans = max(ans,r-l);
        l++;
    }
    cout << ans << "\n";
    return 0;
}

转载自NC224938 加减 - 空白菌 - 博客园 (cnblogs.com)