算法leetcode

力扣1388-3n块披萨

字数统计: 2.3k字   |   阅读时长: 10分
, ,

第 22 场双周赛 D 题

  • 通过猜想和证明，将问题抽象为从 n 个元素的环上选最优的 n / 3 个不相邻的元素
  • 环上取任意多不相邻元素的问题：213. 打家劫舍 II
  • n 个点选不相邻的 k 个，最优解是贪心的做法，但是证明比较难难
  • 用堆维护每个时刻最大的点，在双向循环链表上进行贪心模拟

$1 题目

题目链接

1388. 3n 块披萨

题目描述

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

你挑选 任意 一块披萨。
Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices 表示。

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

数据范围

  • 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 题解

算法 — DP

有两条显然的事实：

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

在以上两条的基础上，可以猜想一个比较大胆的结论：在 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 个。

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

在环上处理取不相邻元素取到最大的问题，也有一个题可以参考 213. 打家劫舍 II
因为首尾不可同时取，可以先将尾去掉，然后做一次非环上问题，再将头去掉，再做一次非环上问题，两次做的结果取最大。

对于非环上问题，状态定义和状态转移如下，在代码中还需要注意边界条件：

1
2
3
dp[i][j] := 考虑到 i，取 j 个可以取到的最大值
dp[i][j] = dp[i - 1][j]     i 不取的情况
           dp[i - 2][j - 1] + slices[i]     i 取的情况

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    // dp[i][j] := 考虑到 i, 取 j 个的答案
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();
        vector<vector<int> > dp(n, vector<int>(n / 3 + 1, -1));
        vector<int> vec(slices.begin(), slices.end() - 1);
        int result1 = _solve(vec, n - 1, n / 3, dp);
        dp.assign(n + 1, vector<int>(n / 3 + 1, -1));
        vec.assign(slices.begin() + 1, slices.end());
        int result2 = _solve(vec, n - 1, n / 3, dp);
        return max(result1, result2);
    }

private:
    int _solve(const vector<int>& slices, int i, int j, vector<vector<int> >& dp)
    {
        if(dp[i][j] != -1) return dp[i][j];

        if(i == 0 || j == 0) return dp[i][j] = 0;
        if(i == 1 && j == 1) return dp[i][j] = slices[i - 1];

        dp[i][j] = _solve(slices, i - 1, j, dp);
        if(i >= 2)
            dp[i][j] = max(dp[i][j], _solve(slices, i - 2, j - 1, dp) + slices[i - 1]);

        return dp[i][j];
    }
};

$3 扩展: 在双向循环链表上做贪心模拟

算法 — 贪心+堆+双向循环链表

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

基本的贪心想法是取最大的两个，如果最大的两个不相邻，则直接取最大的两个是对的，但是两个最大的相邻时就错了，因为不能取相邻的，
所以直接取最大的两个这个贪心做法是错的。但是以此为起点可以进一步往下考虑。

假如是在数组 a 中选最大的两个，记最大的数的位置是 i。结论：两个数的和最大的位置有两种情况

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

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

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

因此 2 个数和最大的位置的两种情况的结论正确。2 可以推广到 k，这个的证明比较难。

基于上述结论，在 n 个中选不相邻的 n / 3 个可以有以下算法

  1. 选 n / 3 次，每次选最大的点 i，同时将 i - 1, i + 1 也取出
  2. 在 i 位置放回一个新点，值为 a[i-1] + a[i+1] - a[i]，参考结论第 2 条。下一步若选了放回的点，则相当于选了 i - 1 和 i + 1，这可以理解为一种后悔机制，先选最大的 i，一般是对的，但是如果 i - 1 和 i + 1 更好，下一步就可以后悔。
  • 每次选择最大的点，用一个最大堆维护。
  • 每次取出 3 个点，放回 1 个点，需要 O(1) 插入删除
    • 可以用双向循环链表，堆中放节点指针，删除的时候只改链接关系，不将节点删除，因为堆中可能还有指针指向那个节点。
    • 也可以用数组模拟链表。
  • i 位置的点可以不做删除，只修改值，i - 1 和 i + 1 需要删掉(标记已删)

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
struct DoubleListNode {
    int val;
    DoubleListNode *next;
    DoubleListNode *prev;
    DoubleListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
};

class DoubleCircleList {
public:
    DoubleCircleList() {
        head = new DoubleListNode(0);
        head -> next = head;
        head -> prev = head;
        tail = head;
        length = 0;
    }

    DoubleListNode* insert(DoubleListNode *pos, int val)
    {
        DoubleListNode *cur = new DoubleListNode(val);
        cur -> next = pos -> next;
        cur -> prev = pos;
        pos -> next -> prev = cur;
        pos -> next = cur;
        if(tail == pos)
            tail = cur;
        ++length;
        return cur;
    }

    bool insertLast(int value) {
        DoubleListNode *cur = new DoubleListNode(value);
        cur -> next = head;
        cur -> prev = tail;
        tail -> next = cur;
        head -> prev = cur;
        tail = cur;
        ++length;
        return true;
    }

    DoubleListNode* delete_(DoubleListNode *pos)
    {
        pos -> prev -> next = pos -> next;
        pos -> next -> prev = pos -> prev;
        DoubleListNode *result = pos -> prev;
        pos = nullptr;
        if(head -> next == head)
            tail = head;
        return result;
    }

    void change(DoubleListNode* pos, int val)
    {
        pos -> val = val;
    }

    bool is_head(DoubleListNode *pos)
    {
        return pos == head;
    }

    DoubleListNode* get_next(DoubleListNode *pos)
    {
        return pos -> next;
    }

    DoubleListNode* get_prev(DoubleListNode *pos)
    {
        return pos -> prev;
    }

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

    DoubleListNode* get_head()
    {
        return head;
    }

private:
    DoubleListNode *head, *tail;
    int length;
};

class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        int n = slices.size();
        DoubleCircleList dclist;
        for(int i: slices) dclist.insertLast(i);
        priority_queue<PID, vector<PID>, Cmp> pq;
        DoubleListNode *it = dclist.get_head();
        vector<DoubleListNode*> deletelist;
        for(int i = 0; i < n; ++i)
        {
            it = dclist.get_next(it);
            pq.push(PID(it -> val, it));
        }
        int result = 0;
        for(int i = 0; i < n / 3; ++i)
        {
            while(pq.top().second -> next -> prev != pq.top().second)
            {
                deletelist.push_back(pq.top().second);
                pq.pop();
            }
            DoubleListNode *cur = pq.top().second;
            pq.pop();
            result += cur -> val;
            int new_val = 0 - cur -> val;
            DoubleListNode *it_left = dclist.get_prev(cur), *it_right = dclist.get_next(cur);
            if(dclist.is_head(it_left)) it_left = dclist.get_prev(it_left);
            if(dclist.is_head(it_right)) it_right = dclist.get_next(it_right);
            new_val += it_left -> val + it_right -> val;
            dclist.delete_(it_left);
            dclist.delete_(it_right);
            dclist.change(cur, new_val);
            //dclist.traverse();
            pq.push(PID(new_val, cur));
        }
        for(DoubleListNode *node: deletelist)
            delete node;
        return result;
    }

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

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