logo标签列表

将数组大小缩减至1的最小成本

c++arraysalgorithmdata-structures
3
给定一个由N个数字组成的数组（不一定排序）。我们可以将任意两个数字合并成一个数字，合并这两个数字的成本等于它们的值之和。任务是找到合并所有数字的总最小成本。
例如： 假设数组A=[1,2,3,4]， 我们可以移除1和2，将它们相加并将总和保留在数组中，此步骤的成本为(1+2)=3。 然后，A=[3,3,4]，成本=3 在第二步中，我们可以将3和3相加，并将总和保留在数组中。此步骤的成本为(3+3)=6。 然后，A=[4,6]，成本=6 在第三步中，我们可以再次从数组中移除这两个元素并将总和保留在数组中。此步骤的成本为(4+6)=6。 现在，A=[10]，成本=10 因此，总成本为19（10+6+3）。 我们需要选择2个最小的元素来最小化总成本。使用最小堆结构是简单的方法。我们将能够以O(1)的时间获取最小元素，插入操作为O(log n)。 这种方法的时间复杂度为O(n log n)。
但我尝试了另一种方法，并且无法找到它失败的实例。基本思路是，我们在任何时候选择的两个最小元素的和将始终大于之前选择的元素对的总和。因此，“temp”数组将始终保持排序，我们将能够以O(1)的时间访问最小元素。 由于我对输入数组进行了排序，然后简单地遍历数组，因此我的方法的复杂度是O(n log n)。
int minCost(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    // temp array will contain the sum of all the pairs of minimum elements
    vector<int> temp;
    // index for arr
    int i = 0;
    // index for temp
    int j = 0;
    int cost = 0;

    // while we have more than 1 element combined in both the input and temp array
    while(arr.size() - i + temp.size() - j > 1) {
        int num1, num2;
        // selecting num1 (minimum element)
        if(i < arr.size() && j < temp.size()) {
            if(arr[i] <= temp[j])
                num1 = arr[i++];
            else
                num1 = temp[j++];
        }
        else if(i < arr.size())
            num1 = arr[i++];
        else if(j < temp.size())
            num1 = temp[j++];

        // selecting num2 (second minimum element)
        if(i < arr.size() && j < temp.size()) {
            if(arr[i] <= temp[j])
                num2 = arr[i++];
            else
                num2 = temp[j++];
        }
        else if(i < arr.size())
            num2 = arr[i++];
        else if(j < temp.size())
            num2 = temp[j++];

        // appending the sum of the minimum elements in the temp array
        int sum = num1 + num2;
        temp.push_back(sum);
        cost += sum;
    }
    return cost;
}

这种方法正确吗？如果不正确，请告诉我我漏掉了什么，以及该算法失败的测试用例。

同一问题的SPOJ链接

1
这种方法正确吗？如何知道您的程序是否存在逻辑错误？仅仅因为它编译通过并不意味着它是无误的。算法只有在被编写成应该实现算法的程序时才能发挥作用。例如，Djikstra最短路径算法没有错误，但如果我实现不正确，则问题在于实现而不是算法本身。 - PaulMcKenzie
欢迎来到 Stack Overflow。请阅读帮助页面，参观 SO，阅读[提问指南]，以及问题清单。最后，请不要滥用无关的标签。例如，这个问题与 Python 有什么关系？ - Some programmer dude
我无法找到我的方法中的逻辑错误，这就是为什么我发布了这个问题。我想知道我的方法在逻辑上哪里出了问题。 - Coder Champ
但我尝试了另一种方法...... -- 好吧，你选择承担了那个负担，而不是坚持使用一个你声称有效的实现（使用堆）。如果你的算法失败了，在写入任何一行代码之前，它应该在纸上显而易见，无需C++代码来证明它会失败。 - PaulMcKenzie
数组不等于向量... - DevSolar
显示剩余7条评论
3个回答
3

这个逻辑对我来说非常可靠... 所有计算的总和都不会减少，因此您只需要相加先前计算出的两个最旧的和、下一个两个元素或最旧的和和下一个元素即可。

我只会简化代码：

#include <vector>
#include <algorithm>
#include <stdio.h>

int hsum(std::vector<int> arr) {
    int ni = arr.size(), nj = 0, i = 0, j = 0, res = 0;
    std::sort(arr.begin(), arr.end());
    std::vector<int> temp;
    auto get = [&]()->int {
        if (j == nj || (i < ni && arr[i] < temp[j])) return arr[i++];
        return temp[j++];
    };
    while ((ni-i)+(nj-j)>1) {
        int a = get(), b = get();
        res += a+b;
        temp.push_back(a + b); nj++;
    }
    return res;
}

int main() {
    fprintf(stderr, "%i\n", hsum(std::vector<int>{1,4,2,3}));
    return  0;
}

这个想法非常好！

另一个改进是注意到正在处理的两个数组（原始数组和保存总和的临时数组）的累计长度在每一步中都会减少。 由于第一步将使用两个输入元素，临时数组在每一步增加一个元素的事实仍然不足以让“行走队列”分配在数组本身中来到读取指针。 这意味着不需要临时数组，并且可以在数组本身中找到求和所需的空间...

int hsum(std::vector<int> arr) {
    int ni = arr.size(), nj = 0, i = 0, j = 0, res = 0;
    std::sort(arr.begin(), arr.end());
    auto get = [&]()->int {
        if (j == nj || (i < ni && arr[i] < arr[j])) return arr[i++];
        return arr[j++];
    };
    while ((ni-i)+(nj-j)>1) {
        int a = get(), b = get();
        res += a+b;
        arr[nj++] = a + b;
    }
    return res;
}

关于SPOJ错误... 我尝试简要搜索了一下这个问题，但没有成功。我尝试生成随机长度的随机数组，并使用从规范直接实现的“暴力”解决方案检查此解决方案的正确性，我相信这个算法是正确的。
我至少知道其中一个编程竞赛（Topcoder），有时会精心设计问题，以便如果使用unsigned，则计算会给出正确的结果，但如果使用int（或如果使用unsigned long long，则不是long long），则计算将不正确，因为存在整数溢出问题。 我不知道SPOJ是否也会做这种无聊的事情（1）...也许这就是某些隐藏测试用例失败的原因...
编辑 通过在SPOJ上使用long long值进行检查，该算法通过了...这是我使用的输入：
#include <stdio.h>
#include <algorithm>
#include <vector>

int main(int argc, const char *argv[]) {
    int n;
    scanf("%i", &n);
    for (int testcase=0; testcase<n; testcase++) {
        int sz; scanf("%i", &sz);
        std::vector<long long> arr(sz);
        for (int i=0; i<sz; i++) scanf("%lli", &arr[i]);

        int ni = arr.size(), nj = 0, i = 0, j = 0;
        long long res = 0;
        std::sort(arr.begin(), arr.end());
        auto get = [&]() -> long long {
            if (j == nj || (i < ni && arr[i] < arr[j])) return arr[i++];
            return arr[j++];
        };
        while ((ni-i)+(nj-j)>1) {
            long long a = get(), b = get();
            res += a+b;
            arr[nj++] = a + b;
        }
        printf("%lli\n", res);
    }
    return 0;
}

PS: 这种计算方法也是构建Huffman树进行熵编码所需的，给定符号频率表，因此它不仅仅是随机练习，而且具有实际应用价值。

(1) 我之所以说“无稽之谈”，是因为在Topcoder上他们从未提供需要65位的问题；因此这不是对溢出的真正关注，而只是为新手设置陷阱。 我认为另一个不好的做法是我在TC上看到的一些问题是精心设计的，以便正确的算法如果使用C++将刚好适合超时限制：只需使用另一种语言（并获得例如2倍的减速），你就无法解决该问题。

非常感谢您的努力！我很喜欢您的解释。 - Coder Champ
0
首先，要保持简单！
当使用优先队列时，问题就变得容易了！
在第一个测试用例中：
1 6 3 20
// after pushing to Q
1 3 6 20
// and sum two top items and pop and push!
(1 + 3) 6 20    cost = 4
(4 + 6) 20      cost = 10 + 4 
(10 + 20)       cost = 30 + 14
30              cost = 44


#include<iostream>
#include<queue>
using namespace std;


int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        priority_queue<long long int, vector<long long int>, greater<long long int>> q;

        for (int i = 0; i < n; ++i) {
            int k;
            cin >> k;
            q.push(k);
        }

        long long int sum = 0;
        while (q.size() > 1) {
            long long int a = q.top();
            q.pop();
            long long int b = q.top();
            q.pop();
            q.push(a + b);
            sum += a + b;
        }

        cout << sum << "\n";
    }
}
0

基本上我们需要按照降序排序列表，然后像这样找到它的成本。

A.sort(reverse=True)
cost = 0
for i in range(len(A)):
    cost += A[i] * (i+1)
return cost
请注意，该问题有一个 c++ 的语言标签。你的代码非常奇怪的 C++。 - Adrian Mole
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接