comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3400-3499/3457.Eat%20Pizzas%21/README.md	贪心 数组 排序

3457. 吃披萨

English Version

题目描述

给你一个长度为 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 * 105
• 1 <= pizzas[i] <= 105
• n 是 4 的倍数。

解法

方法一：贪心 + 排序

根据题目描述，我们每天可以吃 $4$ 个披萨。在奇数天，我们可以得到这 $4$ 个披萨中的最大值，而在偶数天，我们可以得到这 $4$ 个披萨中的第二大值。

因此，我们可以将披萨按重量从小到大排序，一共能吃 $\textit{days} = n / 4$ 天，那么一共有 $\textit{odd} = (\textit{days} + 1) / 2$ 天是奇数天，一共有 $\textit{even} = \textit{days} - \textit{odd}$ 天是偶数天。

考虑奇数天，我们可以选择最大的 $\textit{odd}$ 个披萨，以及最小的 $\textit{odd} \times 3$ 个披萨，增加的重量为 $\sum_{i = n - \textit{odd}}^{n - 1} \textit{pizzas}[i]$。

考虑偶数天，我们在剩余的披萨中，每次贪心地选择最大的两个披萨，以及最小的两个披萨，增加的重量为 $\sum_{i = n - \textit{odd} - 2}^{n - \textit{odd} - 2 \times \textit{even}} \textit{pizzas}[i]$。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组 $\textit{pizzas}$ 的长度。

Python3

class Solution:
    def maxWeight(self, pizzas: List[int]) -> int:
        days = len(pizzas) // 4
        pizzas.sort()
        odd = (days + 1) // 2
        even = days - odd
        ans = sum(pizzas[-odd:])
        i = len(pizzas) - odd - 2
        for _ in range(even):
            ans += pizzas[i]
            i -= 2
        return ans

Java

class Solution {
    public long maxWeight(int[] pizzas) {
        int n = pizzas.length;
        int days = n / 4;
        Arrays.sort(pizzas);
        int odd = (days + 1) / 2;
        int even = days / 2;
        long ans = 0;
        for (int i = n - odd; i < n; ++i) {
            ans += pizzas[i];
        }
        for (int i = n - odd - 2; even > 0; --even) {
            ans += pizzas[i];
            i -= 2;
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long maxWeight(vector<int>& pizzas) {
        int n = pizzas.size();
        int days = pizzas.size() / 4;
        ranges::sort(pizzas);
        int odd = (days + 1) / 2;
        int even = days - odd;
        long long ans = accumulate(pizzas.begin() + n - odd, pizzas.end(), 0LL);
        for (int i = n - odd - 2; even; --even) {
            ans += pizzas[i];
            i -= 2;
        }
        return ans;
    }
};

Go

func maxWeight(pizzas []int) (ans int64) {
	n := len(pizzas)
	days := n / 4
	sort.Ints(pizzas)
	odd := (days + 1) / 2
	even := days - odd
	for i := n - odd; i < n; i++ {
		ans += int64(pizzas[i])
	}
	for i := n - odd - 2; even > 0; even-- {
		ans += int64(pizzas[i])
		i -= 2
	}
	return
}

TypeScript

function maxWeight(pizzas: number[]): number {
    const n = pizzas.length;
    const days = n >> 2;
    pizzas.sort((a, b) => a - b);
    const odd = (days + 1) >> 1;
    let even = days - odd;
    let ans = 0;
    for (let i = n - odd; i < n; ++i) {
        ans += pizzas[i];
    }
    for (let i = n - odd - 2; even; --even) {
        ans += pizzas[i];
        i -= 2;
    }
    return ans;
}