书店网站建设技术风险,内蒙古赤峰市信息网官网,沈阳 网站制作报价,中国建设集团官网给你一个披萨#xff0c;它由 3n 块不同大小的部分组成#xff0c;现在你和你的朋友们需要按照如下规则来分披萨#xff1a;
你挑选 任意 一块披萨。Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。重复上述过程…给你一个披萨它由 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修改为88−97这样我们后面仍然有机会选到这个7也就相当于反悔了对9的选择而去选择了左右两边的两个8。
重复这样的操作直到选取了n/3个元素为止我们就得到了需要的最优解。 为什么我们的反悔操作一定是同时选择左右两个元素呢因为我们是从大到小处理所有元素的所以左右两边的元素一定不大于中间的元素如果我们只选取其中的一个是不可能得到更优解的。 ac code O(nlogn) import java.util.Comparator;
import java.util.PriorityQueue;public class NodeT {public T data;public int index;public NodeT pre;public NodeT next;public Node(){}public Node(T data) {this.data data;}
}
class Solution {public int maxSizeSlices(int[] slices) {PriorityQueueNodeInteger pq new PriorityQueue(new ComparatorNodeInteger() {Overridepublic int compare(NodeInteger o1, NodeInteger 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 i0;in;i) {nodes[i] new Node(slices[i]);nodes[i].index i;pq.add(nodes[i]);}for (int i0;in;i) {nodes[i].pre nodes[(i-1n)%n];nodes[i].next nodes[(i1)%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;}
}
