思路：排序

显然，对于一个数字，他的绝对值越大，操作次数就越多，因此我们需要对数组按照绝对值从小到大排序，然后模拟整个操作过程即可。

时间复杂度

$O(nlogn)$

C++

#include<bits/stdc++.h>
using namespace std;
const int N=1E5+10;
typedef long long ll;
ll a[N],n,k;
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]=abs(a[i]);
    }
    sort(a,a+n);
    int cnt=0;
    for(int i=0;i<n;i++){
        if(k<a[i])break;
        k-=a[i];
        cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

java

import java.util.*;

public class Main{
    public static void main(String[] s){
        Scanner in=new Scanner(System.in);
        long n=in.nextLong(),k=in.nextLong();
        Long[] arr=new Long[(int)n];
        for(int i=0;i<n;i++)arr[i]=in.nextLong();
        Arrays.sort(arr,(Long a, Long b)->{
            return Long.compare(Math.abs(a),Math.abs(b));
        });
        int res=0;
        for(int i=0;i<n;i++){
            if(k>=Math.abs(arr[i])){
                k-=Math.abs(arr[i]);
                res++;
            }
            else break;
        }
        System.out.println(res);
    }
}

Python

import java.util.*;

public class Main{
    public static void main(String[] s){
        Scanner in=new Scanner(System.in);
        long n=in.nextLong(),k=in.nextLong();
        Long[] arr=new Long[(int)n];
        for(int i=0;i<n;i++)arr[i]=in.nextLong();
        Arrays.sort(arr,(Long a, Long b)->{
            return Long.compare(Math.abs(a),Math.abs(b));
        });
        int res=0;
        for(int i=0;i<n;i++){
            if(k>=Math.abs(arr[i])){
                k-=Math.abs(arr[i]);
                res++;
            }
            else break;
        }
        System.out.println(res);
    }
}

题目描述

小美拿到了一个数组，她可以进行最多$k$次操作，每次操作任选一个元素加1或者减1。小美希望最终0的数量尽可能多。你能帮帮她吗?

输入描述

第一行输入2个正整数$n,k$，代表数组大小和小美的操作次数

第二行输入$n$个整数$a_i$，代表小美拿到的数组。 $1\le n\le 10^5$

$1\le k \le 10^{14}$

$-10^9\le a_i\le 10^9$

输出描述

一个整数，代表最终0的数量的最大值。

样例

输入

4 5
-2 3 -2 9

输出

2

说明

对第二个元素操作3次减1，对第三个元素操作2次加1，这样数组变成[-2,0,0,9]。
请注意，方案并不是唯一的。但可以证明，0的数量不会超过2个。