Medium
题目描述
给你一个大小为 n 的整数数组 pizzas，其中 pizzas[i] 表示第 i 个披萨的重量。每天你恰好吃 4 个披萨。由于你惊人的新陈代谢，当你吃重量为 W、X、Y 和 Z 的披萨时，其中 W <= X <= Y <= Z，你只会增加 1 个披萨的重量！
- 在奇数天（从 1 开始索引），你增加重量 Z。
- 在偶数天，你增加重量 Y。
通过最优地吃掉所有披萨，找到你能获得的最大总重量。
注意：保证 n 是 4 的倍数，每个披萨只能吃一次。
示例 1：
输入：pizzas = [1,2,3,4,5,6,7,8]
输出：14
解释：
第 1 天，你吃索引为 [1, 2, 4, 7] 的披萨 = [2, 3, 5, 8]。你增加重量 8。
第 2 天，你吃索引为 [0, 3, 5, 6] 的披萨 = [1, 4, 6, 7]。你增加重量 6。
吃掉所有披萨后获得的总重量是 8 + 6 = 14。
示例 2：
输入：pizzas = [2,1,1,1,1,1,1,1]
输出：3
解释：
第 1 天，你吃索引为 [4, 5, 6, 0] 的披萨 = [1, 1, 1, 2]。你增加重量 2。
第 2 天，你吃索引为 [1, 2, 3, 7] 的披萨 = [1, 1, 1, 1]。你增加重量 1。
吃掉所有披萨后获得的总重量是 2 + 1 = 3。
约束：
4 <= n == pizzas.length <= 2 * 10^51 <= pizzas[i] <= 10^5- n 是 4 的倍数。
解题思路
这是一道贪心策略题目。关键在于理解每天的收益规则：
核心观察：
- 奇数天获得最大值Z，偶数天获得第二大值Y
- 奇数天应该选择3个最小的披萨+1个最大的披萨
- 偶数天应该选择2个最小的披萨+2个最大的披萨
算法思路：
- 将披萨重量排序
- 计算总天数
days = n/4，奇数天数为ceil(days/2) - 使用贪心策略：
- 对于奇数天，从最大的披萨中选1个，从最小的披萨中选3个
- 对于偶数天，从剩余最大的披萨中选2个，从剩余最小的披萨中选2个
实现细节： 使用双指针技术，left指向当前最小披萨，right指向当前最大披萨。根据天数奇偶性决定选择策略，每次选择后更新指针位置。
时间复杂度主要在排序阶段，贪心选择只需要O(n)时间。
代码实现
class Solution {
public:
long long maxWeight(vector<int>& pizzas) {
sort(pizzas.begin(), pizzas.end());
int n = pizzas.size();
int days = n / 4;
int oddDays = (days + 1) / 2;
long long result = 0;
int left = 0, right = n - 1;
// Process odd-numbered days first
for (int i = 0; i < oddDays; i++) {
result += pizzas[right]; // Take the largest
right--;
left += 3; // Skip 3 smallest
}
// Process even-numbered days
int evenDays = days - oddDays;
for (int i = 0; i < evenDays; i++) {
result += pizzas[right - 1]; // Take the second largest
right -= 2; // Skip 2 largest
left += 2; // Skip 2 smallest
}
return result;
}
};
class Solution:
def maxWeight(self, pizzas: List[int]) -> int:
pizzas.sort()
n = len(pizzas)
days = n // 4
odd_days = (days + 1) // 2
result = 0
left, right = 0, n - 1
# Process odd-numbered days first
for i in range(odd_days):
result += pizzas[right] # Take the largest
right -= 1
left += 3 # Skip 3 smallest
# Process even-numbered days
even_days = days - odd_days
for i in range(even_days):
result += pizzas[right - 1] # Take the second largest
right -= 2 # Skip 2 largest
left += 2 # Skip 2 smallest
return result
public class Solution {
public long MaxWeight(int[] pizzas) {
Array.Sort(pizzas);
int n = pizzas.Length;
int days = n / 4;
int oddDays = (days + 1) / 2;
long result = 0;
int left = 0, right = n - 1;
// Process odd-numbered days first
for (int i = 0; i < oddDays; i++) {
result += pizzas[right]; // Take the largest
right--;
left += 3; // Skip 3 smallest
}
// Process even-numbered days
int evenDays = days - oddDays;
for (int i = 0; i < evenDays; i++) {
result += pizzas[right - 1]; // Take the second largest
right -= 2; // Skip 2 largest
left += 2; // Skip 2 smallest
}
return result;
}
}
var maxWeight = function(pizzas) {
pizzas.sort((a, b) => a - b);
const n = pizzas.length;
const days = Math.floor(n / 4);
const oddDays = Math.floor((days + 1) / 2);
let result = 0;
let left = 0, right = n - 1;
// Process odd-numbered days first
for (let i = 0; i < oddDays; i++) {
result += pizzas[right]; // Take the largest
right--;
left += 3; // Skip 3 smallest
}
// Process even-numbered days
const evenDays = days - oddDays;
for (let i = 0; i < evenDays; i++) {
result += pizzas[right - 1]; // Take the second largest
right -= 2; // Skip 2 largest
left += 2; // Skip 2 smallest
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log n) | 主要开销在排序，贪心选择为O(n) |
| 空间复杂度 | O(1) | 只使用常数额外空间（不考虑排序的空间开销） |