給你一個披薩，它由 3n 塊不同大小的部分組成，現在你和你的朋友們需要按照如下規則來分披薩：
- 你挑選?任意?一塊披薩。
- Alice 將會挑選你所選擇的披薩逆時針方向的下一塊披薩。
- Bob 將會挑選你所選擇的披薩順時針方向的下一塊披薩。
- 重復上述過程直到沒有披薩剩下。
每一塊披薩的大小按順時針方向由循環數組?slices?表示。
請你返回你可以獲得的披薩大小總和的最大值。
輸入：slices = [1,2,3,4,5,6] 輸出：10 解釋：選擇大小為 4 的披薩，Alice 和 Bob 分別挑選大小為 3 和 5 的披薩。然后你選擇大小為 6 的披薩，Alice 和 Bob 分別挑選大小為 2 和 1 的披薩。你獲得的披薩總大小為 4 + 6 = 10 。
輸入：slices = [8,9,8,6,1,1] 輸出：16 解釋：兩輪都選大小為 8 的披薩。如果你選擇大小為 9 的披薩，你的朋友們就會選擇大小為 8 的披薩，這種情況下你的總和不是最大的。
提示：
1 <= slices.length <= 500slices.length % 3 == 01 <= slices[i] <= 1000
思路：
首先，每一次選擇都是可以自由選擇披薩，但是選擇完成之后，左右兩邊披薩則是不能選擇，所以可以簡化題目，看成在循環列表中，選取n/3個不連續的元素的最大值。
兩種解法：1、類似于小偷偷家的動態規劃? 2、貪心+優先隊列模擬取數
這里只介紹第2種方法（第1種有空補上。。）
這道題目中，直觀想到的貪心策略是每一步選取最大的一塊。但以[8,9,8,1,2,3]為例，如果我們第一步選取了9，剩下的元素就變成了[1,2,3]，我們最大只能選擇3，這樣的總和就只有12，而顯然選取兩個8可以得到16的總和，是更優的。
如果我們可以反悔就好了。問題是，怎么反悔？在上面的例子中，我們第一步選9之后，如果直接刪除兩個8，那就失去了反悔的機會，因為后面再也不會處理到它們了。所以，我們需要刪除兩個8對應的節點，同時保留它們的信息。信息保留在哪里？只能是9所對應的節點。
我們在選取9之后，將左右兩個節點刪除，同時將9修改為8+8?9=7，這樣我們后面仍然有機會選到這個7，也就相當于反悔了對9的選擇，而去選擇了左右兩邊的兩個8。
重復這樣的操作，直到選取了n/3個元素為止，我們就得到了需要的最優解。
為什么我們的反悔操作一定是同時選擇左右兩個元素呢？因為我們是從大到小處理所有元素的，所以左右兩邊的元素一定不大于中間的元素，如果我們只選取其中的一個，是不可能得到更優解的。
ac code O(nlogn)：
import java.util.Comparator;
import java.util.PriorityQueue;public class Node<T> {public T data;public int index;public Node<T> pre;public Node<T> next;public Node(){}public Node(T data) {this.data = data;}
}
class Solution {public int maxSizeSlices(int[] slices) {PriorityQueue<Node<Integer>> pq = new PriorityQueue<>(new Comparator<Node<Integer>>() {@Overridepublic int compare(Node<Integer> o1, Node<Integer> o2) {return o2.data - o1.data; // 從大到小進行排序}});int n = slices.length;Node[] nodes = new Node[n];int step = 0;int maxStep = n / 3;int ans = 0;boolean[] vis = new boolean[n];for (int i=0;i<n;i++) {nodes[i] = new Node(slices[i]);nodes[i].index = i;pq.add(nodes[i]);}for (int i=0;i<n;i++) {nodes[i].pre = nodes[(i-1+n)%n];nodes[i].next = nodes[(i+1)%n];}while (step < maxStep) {Node cur = pq.poll();if (!vis[cur.index]) {step += 1;ans += (int)cur.data;cur.data = (int)cur.pre.data + (int)cur.next.data - (int)cur.data;vis[cur.pre.index] = true;vis[cur.next.index] = true;// 這里需要注意，需要將前后節點進行刪除。cur.pre = cur.pre.pre;cur.pre.next = cur;cur.next = cur.next.next;cur.next.pre = cur;pq.add(cur); // 后悔操作
// System.out.println(step + " " + cur.index + " " + ans);}}return ans;}
}
