Я пытаюсь вычислить минимальное скалярное произведение для двух массивов / векторов. Ниже приведены подробности:
Проблема: даны две последовательности а1, а2,. , , и 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
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;
}
Сделайте следующие изменения:
замещать vector<int>
от vector<int64_t>
хранить номер в 64-битном целом числе.
использование result = std::inner_product(a.begin(), a.end(), b.begin(), 0LL);
(0LL
предположить, что результат int64_t
)
Проблема в том, что вы храните его в int32_t
и так умножение переполняется.
Других решений пока нет …