3457. 吃披萨

题目描述

给你一个长度为 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⁵
1 <= pizzas[i] <= 10⁵
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}\) 的长度。

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

3457. 吃披萨

题目描述

解法

方法一：贪心 + 排序

评论