力扣1388-3n块披萨

字数统计: 3.4k字 | 阅读时长: 15分

2020-05-25

leetcode428, 一题多解77, 动态规划129, 数据结构173, 模拟15, 证明48

摘要: 一个困难题，问题规约、猜想、构造性证明

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一下第 22 场双周赛 D 题。本题的难点在于通过猜想和证明，将问题规约为打家劫舍问题：从 n 个元素的环上选最优的 n / 3 个不相邻的元素。

此外从 n 个点选不相邻的 k 个，最优解是贪心的做法，用堆维护每个时刻最大的点，在双向循环链表上进行贪心模拟，但是证明比较繁琐。

$1 题目

1388. 3n 块披萨

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

你挑选任意一块披萨。
Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

1
2
3

1 <= slices.length <= 500
slices.length % 3 == 0
1 <= slices[i] <= 1000

示例 1：
输入：slices = [1,2,3,4,5,6]
输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

示例 2：
输入：slices = [8,9,8,6,1,1]
输出：16
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。

示例 3：
输入：slices = [4,1,2,5,8,3,1,9,7]
输出：21

示例 4：
输入：slices = [3,1,2]
输出：3

$2 题解

问题规约：环形数组上取不相邻子序列

梳理问题

有两条显然的事实：

你拿的块数一定是 n / 3，因为 n % 3 == 0。
无论何时，你无法拿相邻的两块。

猜想

在以上两条的基础上，可以猜想一个比较大胆的结论：在 n 块中任意 n / 3 个不相邻的块均可以做得到。

证明（构造性）

证明方法可以用构造性证明，即对应任意 n / 3 个不相邻块，实实在在举出一个可以拿到的办法。从而拿到任意 n / 3 个不相邻快的办法一定存在。

有一串长为 n 的 01 串，其中有 n / 3 个不相邻的 1，下面构造一种方法将这 n / 3 个 1 全都拿到。

首先根据两条显然事实，这个 01 串一定可以划分成若干个 01 交替的串，且边界一定是 0。
其次在边界是 0 的情况下，始终取走边上的 1，取走后，相邻的 1 旁边一定还是 0，该 0 可能属于划分好的另一段(此时两段合并成了1段)，也可能不属于任何一段，如图

构造方法

始终取走边上的 1 的取法可以持续进行下去，直到所有段合并成了1个段并且取完。

因此 n 个当中一定能取到任何不相邻的 n / 3 个。

$\Box$

问题变成了：n 个元素的环上取 n / 3 个不相邻元素，如何取到最大。取不相邻元素如何取到最大，可以参考打家劫舍：不相邻子序列最大和问题。

算法1：动态规划

在环上处理取不相邻元素取到最大的问题，可以参考环形 DP。类似地，因为首尾不可同时取，本题也可以先将尾去掉，然后做一次非环上问题，再将头去掉，再做一次非环上问题，两次做的结果取最大。

对于非环上问题，状态定义为 $dp[i][k]$ 表示考虑到 $i$，$num[0..i]$ 上选取 $k$ 个不相邻元素，可以渠道的最大值。

其中 $i$ 是阶段，$k$ 为附加信息。这样定义的话，目标为 $dp[n - 1][n / 3]$，边界值为 $dp[0][0] = 0, dp[0][1] = nums[0], dp[1][0] = 0, dp[1][1] = \max(nums[0], nums[1])$，当 k > (i + 2) / 2 时，dp[i][k] = 0。

下面考虑状态转移方程，依然分为选和不选 $nums[i]$ 来考虑：

如果选 $nums[i]$，那么 $nums[i - 1]$ 就不能选，且附加信息 $k$ 会加 1，$dp[i][k] = nums[i] + dp[i - 2][k - 1]$。
如果不选 $nums[i]$，那么 $nums[i - 1]$ 可选可不选，且附加信息 $k$ 保持不变，$dp[i][k] = dp[i - 1][k]$

综合考虑，状态转移方程如下：

$dp[i][k] = \max(nums[i] + dp[i - 2][k - 1], dp[i - 1][k])$

代码(C++)

class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();
        int ans1 = solve(slices, 0, n - 2, n / 3);
        int ans2 = solve(slices, 1, n - 1, n / 3);
        return max(ans1, ans2);
    }

private:
    int solve(const vector<int>& nums, int left, int right, int K)
    {
        int n = right - left + 1;
        vector<vector<int>> dp(n, vector<int>(K + 1, 0));
        dp[0][1] = nums[left];
        dp[1][1] = max(nums[left], nums[left + 1]);
        for(int i = 2; i < n; ++i)
        {
            for(int k = 1; k <= min((i + 2) / 2, K); ++k)
            {
                dp[i][k] = max(nums[left + i] + dp[i - 2][k - 1], dp[i - 1][k]);
            }
        }
        return dp[n - 1][K];
    }
};

算法2：反悔贪心、模拟

N 个点取不相邻的最优的 K 个，贪心的做法可以到 $O(N\log N)$，比 DP 的 $O(NK)$ 好，但是证明比较难。

对 K = 2 的分析

首先考虑 $K = 2$。基本的贪心想法是取最大的两个，如果最大的两个不相邻，则直接取最大的两个是对的，但是两个最大的相邻时就错了，因为不能取相邻的，

所以直接取最大的两个这个贪心做法是错的。但是以此为起点可以进一步往下考虑。

假如是在数组 a 中选最大的两个，记最大的数的位置是 $i$。凭感觉可以猜想出以下引理。

引理

两个数的和最大的位置有两种情况：

(1) $i$ 和另一个不相邻的 $j$ (虽然 $a[j]$ 不一定是次大，但是 a[j] > a[i-1] + a[i+1] - a[i])。
(2) $i + 1$ 和 $i - 1$ (虽然 $a[i]$ 最大，但次大与 $a[i]$ 相邻, 且其余的元素中没有比 a[i-1] + a[i+1] - a[i] 更大的了`)。

证明（反证法）

若两数和不是上面两种情况之一，记和最大的两个数为 $a[k], a[l]$。

若 $k, l$ 均与 $i$ 不相邻，则将 $i$ 和任意一个互换，结果都不会更差。
若 $k, l$ 其中之一与 $i$ 不相邻，则将 $i$ 和不相邻的那个互换，结果也不会更差。

因此 2 个数和最大的位置的两种情况的结论正确。

$\Box$

基于以上引理，如果要选 2 个元素，可以用以下的选取策略：

第一个选最大的点 $a[i]$，同时将 $a[i - 1], a[i + 1]$ 也取出，然后将 $a[i-1] + a[i+1] - a[i]$ 放回；
第二个依然选最大的，由于 $a[i-i],a[i+1]$ 已经取出，因此选出的元素自然满足不相邻的要求，但若第二次选出的是后来插入进去的 $a[i-1]+a[i+1]-a[i]$，则是引理的第二种情况，相当于我们选的是 $a[i-1],a[i+1]$。

推广到一般的 K

取两个元素的过程，可以推广到取 k 个，这里我们需要的是 $K=\frac{N}{3}$。

在文章偷k个房间的打家劫舍问题：双向链表维护的反悔贪心策略中我们讨论过反悔贪心的算法及其实现，可以参考。这里我们面对的是同一个问题，选 $K$ 次，每次选取的策略如下：

step1：每次选最大的点 $i$，同时将 $i - 1, i + 1$ 也取出。
step2：在 $i$ 位置放回一个新点，值为 a[i-1] + a[i+1] - a[i]。（参考引理第 2 条。下一步若选了放回的点，则相当于选了 $i - 1$ 和 $i + 1$，这可以理解为一种后悔机制，先选最大的 $i$，一般是对的，但是如果 $i - 1$ 和 $i + 1$ 更好，下一步就可以后悔。）

类似于 $K=2$ 的情况，这个策略的正确性可以通过反证来证明，但是比较繁琐。

维护以上反悔贪心的模拟过程的要点如下：

每次取出 3 个点，放回 1 个点，需要 $O(1)$ 插入删除。因此可以用双向循环链表，堆中放节点指针，删除的时候需要标记已删，因为堆中可能还有指针指向那个节点。
每次选择最大的 $i$，用一个最大堆维护，在弹出时需要判断弹出的指针是否已经被删。
$i$ 位置的点可以不做删除，只修改值，$i - 1$ 和 $i + 1$ 需要删掉，并且标记已删。

通过以上要点分析，维护上述反悔贪心策略的数据结构需要一个堆，以及一个具有标记删除（懒释放）机制的双向循环链表。

代码(C++)

链表部分，基础的双向循环链表（DoubleCircleList 类）可以参考文章【模板】双向链表，这里的代码与模板一样。

懒释放机制（LazyDoubleCircleList 类）可以参考文章【模板】双向链表的懒释放，这里的代码与模板一样。

本题可以作为测试链表以及懒释放机制实现是否正确的测试题。

堆的部分使用 STL 中的组件，堆中的数据为 pair<int, DLNode*>，其中第二个字段为链表节点的指针。

typedef int DLType;
const DLType DLTypeNULL = -1;
const int MAX_LEN = 1e6;

struct DLNode
{
    DLType val;
    DLNode *next;
    DLNode *prev;
    DLNode(DLType x) : val(x), next(nullptr), prev(nullptr) {}
};

class DoubleCircleList
{
protected:
    // head 一直指向 dummy
    // tail 在空表时指向 dummy，否则指向 head 的前一个节点
    DLNode *head, *tail;
    int length;
    int capacity;

public:
    DoubleCircleList(int N=MAX_LEN)
    {
        head = new DLNode(DLTypeNULL);
        head -> next = head;
        head -> prev = head;
        tail = head;
        length = 0;
        capacity = N;
    }

    bool removeHead()
    {
        if(isEmpty())
            return false;
        remove(get_head());
        return true;
    }

    bool removeTail()
    {
        if(isEmpty())
            return false;
        remove(get_tail());
        return true;
    }

    DLType getHead() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_head() -> val;
    }

    DLType getTail() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_tail() -> val;
    }

    bool insertHead(DLType val)
    {
        if(isFull())
            return false;
        insert(head, val);
        return true;
    }

    bool insertTail(DLType val)
    {
        if(isFull())
            return false;
        insert(tail, val);
        return true;
    }

    DLNode* insert(DLNode *pos, DLType val)
    {
        if(!pos || isFull())
            return nullptr;
        DLNode *cur = new DLNode(val);
        cur -> next = pos -> next;
        cur -> prev = pos;
        pos -> next -> prev = cur;
        pos -> next = cur;
        if(tail == pos)
            tail = cur;
        ++length;
        return cur;
    }

    DLType get(DLNode *pos) const
    {
        if(!pos || is_dummy(pos))
            return DLTypeNULL;
        return pos -> val;
    }

    DLNode* remove(DLNode *pos)
    {
        if(!pos || is_dummy(pos) || isEmpty())
            return nullptr;
        if(tail == pos)
            tail = tail -> prev;
        --length;
        pos -> prev -> next = pos -> next;
        pos -> next -> prev = pos -> prev;
        DLNode *result = pos -> next;
        delete pos;
        pos = nullptr;
        if(isEmpty())
            return nullptr;
        if(is_dummy(result))
            result = result -> next;
        return result;
    }

    bool change(DLNode* pos, DLType val)
    {
        if(!pos || is_dummy(pos))
            return false;
        pos -> val = val;
        return true;
    }

    DLNode* get_next(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_tail(pos))
            return get_head();
        return pos -> next;
    }

    DLNode* get_prev(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_head(pos))
            return get_tail();
        return pos -> prev;
    }

    bool is_dummy(DLNode *pos) const
    {
        return pos == head;
    }

    bool is_head(DLNode *pos) const
    {
        return (!isEmpty() && pos == head -> next);
    }

    bool is_tail(DLNode *pos) const
    {
        return (!isEmpty() && pos == tail);
    }

    DLNode* get_tail() const
    {
        if(isEmpty())
            return nullptr;
        return tail;
    }

    DLNode* get_head() const
    {
        if(isEmpty())
            return nullptr;
        return head -> next;
    }


    bool isEmpty() const
    {
        return head == tail;
    }

    int size() const
    {
        return length;
    }

    bool isFull() const
    {
        return length >= capacity;
    }

    void traverse() const
    {
        auto iter = head -> next;
        while(iter != head)
        {
            cout << iter -> val << " ";
            iter = iter -> next;
        }
        cout << endl;
    }
};


class LazyDoubleCircleList: public DoubleCircleList
{
private:
    int lazy_size;
    DLNode *lazy_list;

public:
    LazyDoubleCircleList(int k=MAX_LEN):DoubleCircleList(k)
    {
        lazy_size = 0;
        lazy_list = new DLNode(0);
    }

    bool is_lazy(DLNode* pos) const
    {
        if(!pos || is_dummy(pos) || isEmpty())
            return false;
        return !pos -> prev;
    }

    DLNode* remove_lazy(DLNode *pos)
    {
        if(!pos || is_dummy(pos) || isEmpty())
            return nullptr;
        if(tail == pos)
            tail = tail -> prev;
        --length;
        pos -> prev -> next = pos -> next;
        pos -> next -> prev = pos -> prev;
        DLNode *result = pos -> next;
        // 懒释放
        pos -> next = lazy_list -> next;
        pos -> prev = nullptr; // node -> prev 为空表示该节点已经被懒释放
        ++lazy_size;
        /* 立即释放
         * delete pos;
         * pos = nullptr;
         */
        if(isEmpty())
            return nullptr;
        if(is_dummy(result))
            result = result -> next;
        return result;
    }

    bool removeHead_lazy()
    {
        if(isEmpty())
            return false;
        remove_lazy(get_head());
        return true;
    }

    bool removeTail_lazy()
    {
        if(isEmpty())
            return false;
        remove_lazy(get_tail());
        return true;
    }

    void delete_lazylist()
    {
        DLNode *iter;
        while(lazy_list -> next)
        {
            iter = lazy_list -> next;
            lazy_list -> next = iter -> next;
            delete iter;
        }
        lazy_size = 0;
    }
};


class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();
        LazyDoubleCircleList dclist;
        for(int i: slices) dclist.insertTail(i);
        priority_queue<PID, vector<PID>, Cmp> pq;
        DLNode *it = dclist.get_head();
        vector<DLNode*> deletelist;
        for(int i = 0; i < n; ++i)
        {
            pq.push(PID(it -> val, it));
            it = dclist.get_next(it);
        }
        int result = 0;
        for(int i = 0; i < n / 3; ++i)
        {
            while(dclist.is_lazy(pq.top().second))
                pq.pop();
            DLNode *cur = pq.top().second;
            pq.pop();
            result += cur -> val;
            int new_val = 0 - cur -> val;
            DLNode *it_left = dclist.get_prev(cur), *it_right = dclist.get_next(cur);
            new_val += it_left -> val + it_right -> val;
            dclist.remove_lazy(it_left);
            dclist.remove_lazy(it_right);
            dclist.change(cur, new_val);
            pq.push(PID(new_val, cur));
        }
        dclist.delete_lazylist();
        return result;
    }

private:
    using PID = pair<int, DLNode*>;

    struct Cmp
    {
        bool operator()(const PID& a1, const PID& a2) const
        {
            return a1.first < a2.first;
        }
    };
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法leetcode

力扣1388-3n块披萨

$1 题目

$2 题解

问题规约：环形数组上取不相邻子序列

梳理问题

猜想

证明（构造性）

算法1：动态规划

代码(C++)

算法2：反悔贪心、模拟

对 K = 2 的分析

推广到一般的 K

代码(C++)