计算最小点积 C++

Question

我正在尝试计算两个 arrays/vectors 的最小点积。详情如下：

问题： 给定两个序列 a1, a2, . . . , 和 b1, b2, 。 . . , bn, 找到第二个序列的排列 π 使得 a1, a2, ... 的点积。 . . , 和 bπ1, bπ2, . . . , bπn 最小.

我的逻辑工作正常，但是当我尝试如下输入时，由于整数溢出而失败。我应该使用什么数据类型来满足我的条件 1 ≤ n ≤ 10^3； −10^5 ≤ ai, bi ≤ 10^5 对于所有 1 ≤ i ≤ n

1

99999

上述场景的输出应该是 9999800001 ，但我得到的是 1409865409

#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>

using std::vector;

int64_t min_dot_product(int n, vector<int> a, vector<int> b) {
    int64_t result = 0;
    if (n != 0)
    {
        std::sort(a.begin(), a.end());
        std::sort(b.begin(), b.end());
        std::reverse(a.begin(), a.end());

        /*for (long long int i = 0; i < n; i++) {
            result += a[i] * b[n - 1 - i];
        }*/

        result = std::inner_product(a.begin(), a.end(), b.begin(), 0);
    }
    return result;
}

int main() {
    int n;
    std::cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
    }
    std::cout << min_dot_product(n, a, b) << std::endl;
}

Answer 1

进行以下更改：

将 vector<int> 替换为 vector<int64_t> 以将数字存储为 64 位整数。
使用result = std::inner_product(a.begin(), a.end(), b.begin(), 0LL);
(0LL 建议结果为 int64_t)

问题是您将其存储在 int32_t 中，因此乘法溢出。

计算最小点积 C++

Compute minimum dot product c++

c++

algorithm

dot-product