链接：https://ac.nowcoder.com/acm/contest/20960/1028
来源：牛客网
来源：牛客网
题目描述
小红拿到了一个长度为 n n\n 的数组。她每次操作可以让某个数加 1 或者某个数减 1 。
小红最多能进行 k k\k 次操作。她希望操作结束后，该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗？
小红最多能进行 k k\k 次操作。她希望操作结束后，该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗？
输入描述:
第一行两个正整数 n n\n 和 k k\k 第二行有 n n\n 个正整数 ai a_i\ai 1≤n≤1051 \leq n \leq 10^51≤n≤105 1≤k≤10121 \leq k \leq 10^{12}1≤k≤1012 1≤ai≤1091 \leq a_i \leq 10^91≤ai≤109
输出描述:
不超过 k k\k 次操作之后，数组中可能出现最多次数元素的次数。
示例1
本题是一个枚举的问题，根本问题在于如何枚举能在有限的时间内将正确答案枚举出来，首先需要知道这个出现次数最多的数一定是序列里面某个数。在这里采用枚举左边下标，二分求右边下标的方式去提升速度（既然二分就得排序，在这里从小到大）。
既然采用区间寻找的方式去枚举，那么就需要去验证在该区间里面是否能够满足最小的变化大小小于k的要求。要想验证首先得明白在一个从小到大的序列里面，要想全部变到相同的数并且移动的大小最小那么就一定是位于中间的数，对于中间数有两个的序列来说选取哪一个都是一样的结果。然后将这个区间从中间分隔来分别去求需要移动的大小（通过前缀和的配合快速求出）。由此遍历结束取最大值就是最后的结果。
代码：
//枚举一个l，通过二分快速寻找一个r
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000+10;
ll a[MAXN];
ll sum[MAXN];
ll n, k;
int check(ll l, ll r) {
ll mid = (l+r)>>1;
ll ans = a[mid]*(mid-l+1)-(sum[mid]-sum[l-1])+(sum[r]-sum[mid])-a[mid]*(r-mid);
if (ans<=k) {
return 1;
}
return 0;
}
int main() {
cin>>n>>k;
for (int i=1;i<=n;i++) {
cin>>a[i];
}
sort(a+1, a+n+1);
for (int i=1;i<=n;i++) {
sum[i] = sum[i-1]+a[i];
}
ll ans = -1;
for (ll i=1;i<=n;i++) {
ll l = i, r = n;
ll cnt = -1;
while (l<=r) {
ll mid = (l+r)>>1;
if (check(i, mid)) {
cnt = max(cnt, mid-i+1);
l = mid+1;
} else {
r = mid-1;
}
}
ans = max(ans, cnt);
}
cout<<ans;
return 0;
}
京公网安备 11010502036488号