每日一算：华为-批萨分配问题-EW帮帮网

题目描述

"吃货"和"馋嘴"两人到披萨店点了一份铁盘（圆形）披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不同的奇数块，且肉眼能分辨出大小。

由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：从"吃货"开始，轮流取披萨。除了第一块披萨可以任意选取外，其他都必须从缺口开始选。

他俩选披萨的思路不同。"馋嘴"每次都会选最大块的披萨，而且"吃货"知道"馋嘴"的想法。

问题： 已知披萨小块的数量以及每块的大小，求"吃货"能分得的最大的披萨大小的总和。

解题思路

关键观察：

圆形转线性：吃货第一步可以任意选择，这会将圆形披萨变成线性数组
博弈策略：吃货知道馋嘴总是选最大的，可以利用这个信息制定最优策略
动态规划：后续变成经典的区间博弈问题

算法步骤：

枚举吃货第一块的所有可能选择
对于每种选择，将剩余部分转化为线性博弈问题
使用动态规划求解最优策略
返回所有可能中的最大值

代码实现/C++

#include <iostream>
#include <vector>
#include <algorithm>

class PizzaGame {
private:
    // 解决线性数组的博弈问题
    // player: 0=吃货, 1=馋嘴
    // 返回吃货能获得的最大收益
    int solveLinear(std::vector<int>& arr, int left, int right, int player,
                   std::vector<std::vector<std::vector<int>>>& memo) {
        if (left > right) return 0;
        
        if (memo[left][right][player] != -1) {
            return memo[left][right][player];
        }
        
        int result;
        if (player == 0) { // 吃货的回合
            // 吃货选择能让自己最终收益最大的策略
            result = std::max(
                arr[left] + solveLinear(arr, left + 1, right, 1, memo),
                arr[right] + solveLinear(arr, left, right - 1, 1, memo)
            );
        } else { // 馋嘴的回合
            // 馋嘴总是选最大的
            if (arr[left] >= arr[right]) {
                result = solveLinear(arr, left + 1, right, 0, memo);
            } else {
                result = solveLinear(arr, left, right - 1, 0, memo);
            }
        }
        
        return memo[left][right][player] = result;
    }
    
public:
    int maxPizzaForChihuo(std::vector<int>& pizzaSizes) {
        int n = pizzaSizes.size();
        int maxResult = 0;
        
        // 枚举第一块披萨的选择
        for (int start = 0; start < n; start++) {
            int currentResult = pizzaSizes[start];
            
            if (n > 1) {
                // 构建剩余的线性数组
                std::vector<int> remaining;
                for (int i = 1; i < n; i++) {
                    remaining.push_back(pizzaSizes[(start + i) % n]);
                }
                
                // 初始化记忆化数组
                int remainSize = remaining.size();
                std::vector<std::vector<std::vector<int>>> memo(
                    remainSize, 
                    std::vector<std::vector<int>>(remainSize, 
                        std::vector<int>(2, -1))
                );
                
                // 解决剩余的线性博弈问题（馋嘴先手）
                currentResult += solveLinear(remaining, 0, remainSize - 1, 1, memo);
            }
            
            maxResult = std::max(maxResult, currentResult);
        }
        
        return maxResult;
    }
};

测试用例

int main() {
    PizzaGame game;
    
    // 测试用例1: [1, 3, 7, 5, 2]
    std::vector<int> pizza1 = {1, 3, 7, 5, 2};
    std::cout << "测试1: [1,3,7,5,2] -> " 
              << game.maxPizzaForChihuo(pizza1) << std::endl;
    // 输出: 11 (选择7开始，然后得到7+2+1+1=11)
    
    // 测试用例2: [2, 1, 3, 4, 6, 5, 7]  
    std::vector<int> pizza2 = {2, 1, 3, 4, 6, 5, 7};
    std::cout << "测试2: [2,1,3,4,6,5,7] -> " 
              << game.maxPizzaForChihuo(pizza2) << std::endl;
    
    // 测试用例3: [10, 1, 2, 3, 4]
    std::vector<int> pizza3 = {10, 1, 2, 3, 4};
    std::cout << "测试3: [10,1,2,3,4] -> " 
              << game.maxPizzaForChihuo(pizza3) << std::endl;
    // 输出: 14 (选择10开始，然后得到10+4=14)
    
    return 0;
}

复杂度分析

时间复杂度： O(n³)
- 外层枚举起点：O(n)
- 内层动态规划：O(n²)
- 总体：O(n³)
空间复杂度： O(n²)
- 记忆化数组空间

解题要点

关键洞察：

圆形特殊性：第一步可以任意选择，将圆形转化为线性问题
对手策略：利用已知的对手贪心策略制定最优方案
状态转移：区间DP的经典应用

易错点：

忘记考虑圆形数组的环形特性
没有正确处理博弈双方的不同策略
边界条件处理不当

每日一算：华为-批萨分配问题