2024年4月13日美团春招实习试题【第二题:最多0的个数】-题目+题解+在线评测【贪心】

题目描述：

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

输入描述

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

第二行输入n个整数ai，代表塔子哥拿到的数组。 1≤n≤10⁵

1≤k≤10¹⁴

−10⁹≤ai≤10⁹

输出描述

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

样例

输入

4 5
-2 3 -2 9
1
2

输出

2
1

说明

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

OJ链接
https://codefun2000.com/p/P1820

解题思路一：贪心，将所有负数变为正数，然后排序。nums.sort(key = lambda x: abs(x))

n, k = map(int, input().split())
nums = list(map(int, input().split()))
for i in range(len(nums)):
    if nums[i] < 0:
        nums[i] = -nums[i]
nums.sort()
ans = 0
for i in range(len(nums)):
    if nums[i] == 0:
        ans += 1
    else:
        if k >= nums[i]:
            k -= nums[i]
            ans += 1
        else:
            break
print(ans)

# 同意
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(key = lambda x: abs(x))
ans = 0
s = 0
for x in a:
    s += abs(x)
    if s > k:
        break
    ans += 1
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

时间复杂度：O(nlogn) 排序
空间复杂度：O(1)

解题思路二：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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O(nlogn) 排序
空间复杂度：O(1)

解题思路三：java

import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long k = in.nextLong();
        long[] a = new long[n];
        for(int i=0; i<n; i++){
            a[i] = Math.abs(in.nextLong());
        }
        Arrays.sort(a);
        long count = 0L;
        long sum = 0L;
        for(int i=0; i<n; i++){
            sum += a[i];
            if(sum<=k){
                count++;
            }else{
                break;
            }
        }
        System.out.println(count);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

时间复杂度：O(nlogn) 排序
空间复杂度：O(1)