显然,对于一个数字,他的绝对值越大,操作次数就越多,因此我们需要对数组按照绝对值从小到大排序,然后模拟整个操作过程即可。
时间复杂度
O(nlogn)
C++
小美拿到了一个数组,她可以进行最多k次操作,每次操作任选一个元素加1或者减1。小美希望最终0的数量尽可能多。你能帮帮她吗?
第一行输入2个正整数n,k,代表数组大小和小美的操作次数
第二行输入n个整数ai,代表小美拿到的数组。 1≤n≤105
1≤k≤1014
−109≤ai≤109
一个整数,代表最终0的数量的最大值。
输入
4 5
-2 3 -2 9
输出
2
说明
对第二个元素操作3次减1,对第三个元素操作2次加1,这样数组变成[-2,0,0,9]。
请注意,方案并不是唯一的。但可以证明,0的数量不会超过2个。