Skip to content

3457. Eat Pizzas!

SourceWeekly Contest 437 Q2DifficultyMediumRating1704

Description

You are given an integer array pizzas of size n, where pizzas[i] represents the weight of the ith pizza. Every day, you eat exactly 4 pizzas. Due to your incredible metabolism, when you eat pizzas of weights W, X, Y, and Z, where W <= X <= Y <= Z, you gain the weight of only 1 pizza!

  • On odd-numbered days (1-indexed), you gain a weight of Z.
  • On even-numbered days, you gain a weight of Y.

Find the maximum total weight you can gain by eating all pizzas optimally.

Note: It is guaranteed that n is a multiple of 4, and each pizza can be eaten only once.

 

Example 1:

Input: pizzas = [1,2,3,4,5,6,7,8]

Output: 14

Explanation:

  • On day 1, you eat pizzas at indices [1, 2, 4, 7] = [2, 3, 5, 8]. You gain a weight of 8.
  • On day 2, you eat pizzas at indices [0, 3, 5, 6] = [1, 4, 6, 7]. You gain a weight of 6.

The total weight gained after eating all the pizzas is 8 + 6 = 14.

Example 2:

Input: pizzas = [2,1,1,1,1,1,1,1]

Output: 3

Explanation:

  • On day 1, you eat pizzas at indices [4, 5, 6, 0] = [1, 1, 1, 2]. You gain a weight of 2.
  • On day 2, you eat pizzas at indices [1, 2, 3, 7] = [1, 1, 1, 1]. You gain a weight of 1.

The total weight gained after eating all the pizzas is 2 + 1 = 3.

 

Constraints:

  • 4 <= n == pizzas.length <= 2 * 105
  • 1 <= pizzas[i] <= 105
  • n is a multiple of 4.

Solutions

Solution 1: Greedy + Sorting

Thinking

Each day we eat four pizzas: the max on odd days, the second max on even days. \(n\) is a multiple of \(4\) up to \(2\times 10^5\), so groupings cannot be searched.

Odd days should claim the largest pizzas; even days must “waste” one larger pizza to take the second largest. After sorting, those contributions sit at fixed indices.

Let \(\textit{odd}=\lceil\textit{days}/2\rceil\). Add the largest \(\textit{odd}\) pizzas, then from the remainder take every other pizza as an even-day second maximum.

According to the problem description, we can eat \(4\) pizzas each day. On odd days, we get the maximum value among these \(4\) pizzas, and on even days, we get the second largest value among these \(4\) pizzas.

Therefore, we can sort the pizzas by weight in ascending order. We can eat for \(\textit{days} = n / 4\) days, with \(\textit{odd} = (\textit{days} + 1) / 2\) days being odd days and \(\textit{even} = \textit{days} - \textit{odd}\) days being even days.

For odd days, we can choose the largest \(\textit{odd}\) pizzas and the smallest \(\textit{odd} \times 3\) pizzas, with the increased weight being \(\sum_{i = n - \textit{odd}}^{n - 1} \textit{pizzas}[i]\).

For even days, among the remaining pizzas, we greedily choose the largest two pizzas and the smallest two pizzas each time, with the increased weight being \(\sum_{i = n - \textit{odd} - 2}^{n - \textit{odd} - 2 \times \textit{even}} \textit{pizzas}[i]\).

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array \(\textit{pizzas}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

Comments