OJ练习之加减（中等偏难）
加减
题号：NC224938
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
小红拿到了一个长度为 n 的数组。她每次操作可以让某个数加 1 或者某个数减 1 。
小红最多能进行 k 次操作。她希望操作结束后，该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗？
输入描述:
第一行两个正整数 n 和 k 第二行有 n 个正整数 ai 1≤n≤10^5 1≤k≤10^12 1≤ai≤10^9输出描述:
不超过 k 次操作之后，数组中可能出现最多次数元素的次数。示例1
输入
5 3 6 3 20 8 1输出
2说明
共 3 次操作如下： 第一个数加一。 第二个数加一。 第四个数减一。 数组变成了 7 4 20 7 1 ，共有 2 个相同的数： 7 。 可以证明， 2 为最优解。另外，此上操作并不是唯一的操作。题解（前缀和+滑动窗口+贪心）：
#include<iostream>#include<algorithm>usingnamespacestd;// k已经超出了int的范围，ai涉及到加减操作，很容易超出int范围，所以直接使用long longtypedeflonglongLL;constintN=1e5+10;LL n,k;LL arr[N];LL sum[N];LLcal(intleft,intright){// 选取区间内中间下标，对于区间内偶数个来说，选中间两个的任意一个结果都一样intmid=(left+right)/2;// 区间内：mid左边的个数×a[mid]-mid左边的和+mid右边和和 - mid右边的个数×a[mid]return(mid-left)*arr[mid]-(sum[mid-1]-sum[left-1])+(sum[right]-sum[mid])-(right-mid)*arr[mid];// 根据规律，总结出的公示可以直接O(1)出结果}intmain(){cin>>n>>k;// 将n个数存入，从下标1开始存入for(inti=1;i<=n;i++)cin>>arr[i];// 将n个数按照从小到大排序sort(arr+1,arr+1+n);// 将前i个数的和按照对应下标存入sum数组里备用for(inti=1;i<=n;i++)sum[i]=sum[i-1]+arr[i];intleft=1,right=1;intret=1;// 根据题意，ret最小也是1while(right<=n){// cal用来获取将区间所有数都变成同一个数的最小加减次数，即最小代价LL cost=cal(left,right);while(cost>k)// 如果最小代价比规定的都大，继续寻找更小的可能{left++;// 再扩大区间代价还会增大，要让left右移cost=cal(left,right);}// 更新retret=max(ret,right-left+1);// 当然选择满足的区间差值最大的right++;// 继续尝试寻找更优解}cout<<ret<<endl;return0;}