1044 加减 - 大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge

1044: 加减

时间限制：1.000s

内存限制：128MB

提交通过: 4 提交: 5 统计

小红拿到了一个长度为

n\

的数组。她每次操作可以让某个数加 1 或者某个数减 1 。
小红最多能进行

k\

次操作。她希望操作结束后，该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗？

第一行两个正整数

n\

和

k\

第二行有

n\

个正整数$a_i$

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

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

5 3
6 3 20 8 1

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

二分前缀和

提交