跳转至

2600. K 件物品的最大和

题目描述

袋子中装有一些物品，每个物品上都标记着数字 1 、0 或 -1 。

给你四个非负整数 numOnes 、numZeros 、numNegOnes 和 k 。

袋子最初包含：

  • numOnes 件标记为 1 的物品。
  • numZeros 件标记为 0 的物品。
  • numNegOnes 件标记为 -1 的物品。

现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中，物品上所标记数字之和的最大值。

 

示例 1：

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
输出：2
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 2 件标记为 1 的物品，得到的数字之和为 2 。
可以证明 2 是所有可行方案中的最大值。

示例 2：

输入：numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
输出：3
解释：袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 3 件标记为 1 的物品，1 件标记为 0 的物品，得到的数字之和为 3 。
可以证明 3 是所有可行方案中的最大值。

 

提示：

  • 0 <= numOnes, numZeros, numNegOnes <= 50
  • 0 <= k <= numOnes + numZeros + numNegOnes

解法

方法一：贪心

思考

三种标记的取值固定，若枚举取了几件 \(1\)、几件 \(0\)、几件 \(-1\)，组合数随 \(k\) 线性增长。题目要求恰好取 \(k\) 件且和最大，而 \(k\) 与各计数均不超过 \(50\)，穷举可行，但并无必要。

和由 \(1\)、\(0\)、\(-1\) 线性叠加，多取一件 \(1\) 严格优于多取一件 \(0\)，多取一件 \(0\) 又优于多取一件 \(-1\)。因此最优策略唯一：先取尽 \(1\)，不足再取 \(0\)，仍不足才取 \(-1\)。

比较 \(k\) 与 \(\textit{numOnes}\)、\(\textit{numZeros}\) 即可在常数时间内落到上述三段之一，无需真正构造选取方案。

根据题目描述，我们应该尽可能多地取标记为 \(1\) 的物品，然后取标记为 \(0\) 的物品，最后取标记为 \(-1\) 的物品。

因此：

  • 如果袋子中的物品标记为 \(1\) 的数量大于等于 \(k\)，那么取 \(k\) 件物品，数字之和为 \(k\)；
  • 如果袋子中的物品标记为 \(1\) 的数量小于 \(k\)，那么取 \(\textit{numOnes}\) 件物品，数字之和为 \(\textit{numOnes}\)；如果标记为 \(0\) 的物品数量大于等于 \(k - \textit{numOnes}\)，那么再取 \(k - \textit{numOnes}\) 件物品，数字之和还是 \(\textit{numOnes}\)；
  • 否则，我们再从标记为 \(-1\) 的物品中取 \(k - \textit{numOnes} - \textit{numZeros}\) 件物品，数字之和为 \(\textit{numOnes} - (k - \textit{numOnes} - \textit{numZeros})\)。

时间复杂度 \(O(1)\)，空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
8
9
class Solution:
    def kItemsWithMaximumSum(
        self, numOnes: int, numZeros: int, numNegOnes: int, k: int
    ) -> int:
        if numOnes >= k:
            return k
        if numZeros >= k - numOnes:
            return numOnes
        return numOnes - (k - numOnes - numZeros)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (numOnes >= k) {
            return k;
        }
        if (numZeros >= k - numOnes) {
            return numOnes;
        }
        return numOnes - (k - numOnes - numZeros);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (numOnes >= k) {
            return k;
        }
        if (numZeros >= k - numOnes) {
            return numOnes;
        }
        return numOnes - (k - numOnes - numZeros);
    }
};

1
2
3
4
5
6
7
8
9
func kItemsWithMaximumSum(numOnes int, numZeros int, numNegOnes int, k int) int {
    if numOnes >= k {
        return k
    }
    if numZeros >= k-numOnes {
        return numOnes
    }
    return numOnes - (k - numOnes - numZeros)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function kItemsWithMaximumSum(
    numOnes: number,
    numZeros: number,
    numNegOnes: number,
    k: number,
): number {
    if (numOnes >= k) {
        return k;
    }
    if (numZeros >= k - numOnes) {
        return numOnes;
    }
    return numOnes - (k - numOnes - numZeros);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn k_items_with_maximum_sum(
        num_ones: i32,
        num_zeros: i32,
        num_neg_ones: i32,
        k: i32,
    ) -> i32 {
        if num_ones > k {
            return k;
        }

        if num_ones + num_zeros > k {
            return num_ones;
        }

        num_ones - (k - num_ones - num_zeros)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Solution {
    public int KItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (numOnes >= k) {
            return k;
        }
        if (numZeros >= k - numOnes) {
            return numOnes;
        }
        return numOnes - (k - numOnes - numZeros);
    }
}

评论