4

我们得到一个数字序列a。序列n的减少a被定义为替换元素a[i]和。a[i+1]max(a[i],a[i+1])

每个归约操作的成本定义为max(a[i],a[i+1])。减少后得到n-1一个长度序列1。

现在我们的目标是打印给定序列的最优缩减的成本，a使得长度为 1 的结果序列具有最小成本。

例如：

1

2

3

Output :

5

O(N^2) 解决方案是微不足道的。有任何想法吗？

EDIT1：人们在问我的想法，所以我的想法是成对遍历序列，并为每一对检查成本，最后以最低成本减少对。

1 2 3
 2 3     <=== Cost is 2

所以将上面的序列减少到

2 3

现在再次遍历序​​列，我们得到成本为 3

2 3
 3       <=== Cost is 3

所以总成本是 2+3=5

上面的算法是 O(N^2)。这就是为什么我要求一些更优化的想法。

4

4 回答 4

2

O(n)解决方案：

高水平：

基本思想是重复合并任何e小于其邻居ns和nl最小邻居的元素ns。这产生了最小的成本，因为合并的成本和结果都是max(a[i],a[i+1])，这意味着没有合并可以使元素比当前更小，因此最便宜的合并可能e是 with ns，并且该合并不会增加任何其他的成本可能的合并。

这可以通过一次通过算法来完成，方法是将数组中的一堆元素按降序排列。我们将当前元素与它的两个邻居（一个是堆栈的顶部）进行比较，并执行适当的合并，直到我们完成。

伪代码：

stack = empty
for pos = 0 to length
  // stack.top > arr[pos] is implicitly true because of the previous iteration of the loop
  if stack.top > arr[pos] > arr[pos+1]
    stack.push(arr[pos])
  else if stack.top > arr[pos+1] > arr[pos]
    merge(arr[pos], arr[pos+1])
  else while arr[pos+1] > stack.top > arr[pos]
    merge(arr[pos], stack.pop)

Java代码：

Stack<Integer> stack = new Stack<Integer>();
int cost = 0;
int arr[] = {10,1,2,3,4,5};
for (int pos = 0; pos < arr.length; pos++)
  if (pos < arr.length-1 && (stack.empty() || stack.peek() >= arr[pos+1]))
    if (arr[pos] > arr[pos+1])
      stack.push(arr[pos]);
    else
      cost += arr[pos+1]; // merge pos and pos+1
  else
  {
    int last = Integer.MAX_VALUE; // required otherwise a merge may be missed
    while (!stack.empty() && (pos == arr.length-1 || stack.peek() < arr[pos+1]))
    {
      last = stack.peek();
      cost += stack.pop(); // merge stack.pop() and pos or the last popped item
    }
    if (last != Integer.MAX_VALUE)
    {
      int costTemp = Integer.MAX_VALUE;
      if (!stack.empty())
        costTemp = stack.peek();
      if (pos != arr.length-1)
        costTemp = Math.min(arr[pos+1], costTemp);
      cost += costTemp;
    }
  }
System.out.println(cost);
于 2013-03-05T09:05:09.097 回答
0

If you don't consider it cheating to sort the list, then do it in n log n time and then merge the first two entries recursively. The total cost in this case will be the sum of the entries minus the smallest entry. This is optimal since

  1. the cost will be the sum of n-1 entries (with repeats allowed)
  2. the ith smallest entry can appear at most i-1 times in the cost function

The same fundamental idea works even if the list isn't sorted. An optimal solution is to merge the smallest element with its smallest neighbor. To see that this is optimal, note that

  1. the cost will be the sum of n-1 entries (with repeats allowed)
  2. entry a_i can appear at most j-1 times in the cost function, where j is the length of the longest consecutive subsequence containing a_i such that a_i is the maximum element of the subsequence

In the worst case, the sequence is decreasing and the time is O(n^2).

于 2013-03-05T05:38:19.427 回答
0

贪婪的方法确实有效。

您始终可以使用较小的邻居来减少最小的数字。

证明：我们必须在某个时候减少最小的数字。任何减少邻居都会使邻居的值至少相同（可能）更大，因此减少最小元素 a[i] 的操作将始终具有成本 c>=min(a[i-1], a[i+ 1])

现在我们需要

  1. 快速查找/删除最小数字
  2. 找到它的邻居

我会选择 2 个 RMQ。执行操作 2 作为二进制搜索。这给了我们 O(N * log^2(N))

编辑：第一个 RMQ - 值。当您删除一个元素时，会在
第二个 RMQ 中放置一些大值 - “存在”。0 或 1（值存在/不存在）。要找到 a[i] 的 [例如] 左邻居，您需要找到最大的l，即sum[l,i-1] = 1。

于 2013-03-05T02:58:34.607 回答
0

如果您的意思是减少“计算成本”的“成本”，即需要时间的操作max(a[i],a[i+1])或只是您想要计算的东西，我会感到困惑。如果是后者，那么下面的算法优于O(n^2)：

  1. 对列表进行排序，或者更准确地说，定义b[i]sta[b[i]]是排序列表：如果可以使用 RADIX 排序，则为 O(n)，否则为 O(n log n)。
  2. 从i排序列表中的倒数第二项开始：如果左/右低于 i，则执行归约：每个项目 O(1)，从 2 更新列表，总共 O(n)。

我不知道这是否是最佳解决方案，但整数的 O(n) 和 O(n log n)，否则。

编辑：意识到删除预计算步骤使其变得更加简单

于 2013-03-05T02:05:58.820 回答