慢和算法

Question

假设我们有一个包含 N 个数字的列表并重复以下操作，直到我们只剩下一个数字： 选择任意两个连续的数字并用它们的总和替换它们。此外，我们将每个操作的惩罚与等于新数字的值相关联，并将整个列表的惩罚称为每个操作的惩罚之和。

注意：连续数字表示它们在数组中的索引是连续的，而不是它们的值是连续的。例如，给定列表 [1, 2, 3, 4, 5]，我们可以选择 2 和 3 进行第一次操作，这会将列表转换为 [1, 5, 4, 5] 并产生 5 的惩罚. 这个问题的目标是找到给定输入的最坏可能的惩罚。

约束条件： 1 ? 否 10^6 1 ? 艾？10^7，其中 *Ai 表示数组的第 i 个初始元素。所有测试用例的 N 值总和不会超过 5 * 10^6。

Example
arr = [4, 2, 1, 3]
output = 23
First, add 4 + 2 for a penalty of 6. Now the array is [6, 1, 3]
Add 6 + 1 for a penalty of 7. Now the array is [7, 3]
Add 7 + 3 for a penalty of 10. The penalties sum to 23.

int getTotalTime(int[] arr) {}

Answer 1

这是一个贪心问题。其背后的关键是要注意，我们必须始终遵循每次迭代中可能的最大总和。就您而言[4, 2, 1, 3]，第一个最大的金额是6，然后7然后10。

\n\n

当最大的和出现多次时，问题就来了，例如，那么你必须选择是否从或[5, 3, 7, 1]开始更好。[5, 3][7, 1]

\n\n

#include <bits/stdc++.h>\nusing namespace std;\n\nint n = 6;                       //array size\nint a[] = {2, 1, 7, 1, 5, 3};    //array\n\nvector<pair<int, int>> v;        //positions we will analyse\n\nvoid analyse(){                  //this method gets the positions with biggest sum\n    int sum = 0;\n    for(int i = 1; i < n; i++) sum = max(sum, a[i - 1] + a[i]);\n    for(int i = 1; i < n; i++) if(a[i - 1] + a[i] == sum) v.push_back(make_pair(i - 1, i));\n}\n\nint evaluate_penalty(int i, int j){   //given a position, this method finds\n    int l = i, r = j;                 //the biggest penalty starting there\n    int penalty = a[i] + a[j];\n    int val = penalty;\n    while(i != 0 || j != n - 1){\n        if(l > 0 && r < n - 1) {\n            if(a[l - 1] > a[r + 1]) l--;\n            else r++;\n        }\n        else if(l > 0) l--;\n        else r++;\n\n        val += (l != i ? a[l] : 0) + (r != j ? a[r] : 0);\n        penalty += val;\n        i = l; j = r;\n    }\n    return penalty;\n}\n\nint max_penalty(){            //this method finds the biggest penalty\n    v.clear();                //within all the possible starting positions.\n    analyse();\n    int maxPenalty = 0;\n    for(int i = 0; i < v.size(); i++){\n        maxPenalty = max(maxPenalty, evaluate_penalty(v[i].first, v[i].second));\n    }\n    return maxPenalty;\n}\n\nint main(){\n    cout<<max_penalty()<<endl;\n    return 0;\n}\n

\n\n

复杂度为O(n\xc2\xb2)，但在大多数情况下，它将是O(n)。鉴于两个连续数字之间的最大和是s，复杂性取决于有多少对连续数字相加s。如果只有一个（如您的示例中所示）[4, 2, 1, 3]，它将在一次迭代中完成，因此 O(n)。如果数组类似于[1, 1, 1, 1, 1, ..., 1]，则需要 O(n\xc2\xb2)。

\n