алгоритм — вычисление минимального точечного произведения Переполнение стека

Я пытаюсь вычислить минимальное скалярное произведение для двух массивов / векторов. Ниже приведены подробности:

Проблема: даны две последовательности а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;
}

1

Решение

Сделайте следующие изменения:

  1. замещать vector<int> от vector<int64_t> хранить номер в 64-битном целом числе.

  2. использование result = std::inner_product(a.begin(), a.end(), b.begin(), 0LL);
    (0LL предположить, что результат int64_t)

Проблема в том, что вы храните его в int32_t и так умножение переполняется.

3

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]