CodeJam最小标量产品问题

Question

我在练习这个问题，很快就找到了正确的算法，但在实现它的过程中，我遇到了一些奇怪的事情。起初，我意识到我被整数类型的溢出所困扰，所以开始使用__int64。这时我注意到了下一件奇怪的事情。首先，这是我的代码。。。

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
const string cInputFileName = "E:\CodeJamInputs\d-large-practice.in";
const string cOutputFileName = "E:\CodeJamInputs\d-large-practice.out.txt";
__int64 FindSmallestProductOfSums(const vector<int> &iVec1, const vector<int> &iVec2)
{
vector<int> v1 = iVec1;
vector<int> v2 = iVec2;
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end(), greater<int>());
__int64 productOfSumsA = inner_product(v1.begin(), v1.end(), v2.begin(), 0);
__int64 productOfSumsB = 0;
for(vector<int>::size_type i = 0; i < v1.size(); ++i)
productOfSumsB += (__int64)v1[i] * (__int64)v2[i];
return productOfSumsB;
}
int _tmain(int argc, _TCHAR* argv[])
{
ifstream inputFile(cInputFileName, ifstream::in);
ofstream outputFile(cOutputFileName, ofstream::out);
if(inputFile.is_open() && outputFile.is_open())
{
int numCases;
inputFile >> numCases;
for(int i = 0; i < numCases; ++i)
{
int vectorSizes;
inputFile >> vectorSizes;
vector<int> vec1, vec2;
for(int j = 0; j < vectorSizes; ++j)
{
int value;
inputFile >> value;
vec1.push_back(value);
}
for(int j = 0; j < vectorSizes; ++j)
{
int value;
inputFile >> value;
vec2.push_back(value);
}
__int64 smallestProductOfSums = FindSmallestProductOfSums(vec1, vec2);
outputFile << "Case #" << (i + 1) << ": " << smallestProductOfSums;
outputFile << endl;
}
}
inputFile.close();
outputFile.close();
}

正如你所看到的，我对这两个向量进行了两次计算。一个使用STL inner_product，另一个只是手动迭代。因此，愚蠢的是，对于问题中的大数据集，inner_product方法会导致错误的返回，而手工方法是正确的。进入STL代码，在我看来，溢出确实发生了，因为Ty-Val变量似乎是一个int，当然这是结果累积的地方。

所以，我想知道的是，对于那些使用inner_product解决了这个问题的人来说，你认为有什么区别？我试着将0LL作为初始参数传递给咯咯笑，事实上，它确实得到了不同的答案，但仍然不是正确的答案。奇怪的是，在我添加显式__int64强制转换之前，它确实得到了与hand方法相同的答案。所以这里肯定有一些奇怪的类型和溢出，只是不确定是什么。不管怎样，无论是小型还是大型，我都得到了正确的答案，但我只是看到有些人使用inner_product，而我无法使用它。让我重新表述一下。。。inner_product适用于小型数据集，但不适用于大型数据集，我的解决方案适用于小型和大型数据集。

以下是问题中每种情况的输出(大数据集总共10个)。对于每种情况，都有三个输出。第一种是手工计算的方法(正确答案)，第二种是使用init为"0"的inner_product(错误答案)，而第三种是使用初始化为"0LL"的inner-product(不正确答案)。此外，只是凭直觉，我也编译为x64目标，但结果是一样的。

案例1:-7839202227936案例1:-886912736案例1:-1104693507808

案例2:7999201712083案例2:1972606931案例2:1127254038483

案件#3：-1313429236847案例3：830755729案例3：-17562903407

案例4:-3710387739618案例4:46404126案例4:-8730309090

案例5:-3414920765916案例5:-421765956案例5:82026144220

案件#6:-1271937742993案件#6:-627423377案例6:-3069219449

案件#7:-19694394407029案件7：-1594352757案例#7:-40249058421

案件#8:-184842427866案例8:1208215078案例8:-101871000026

案例9：-404533757860案件编号9：1325434972案例9：-10604747428

案件#10:838783451371案例#10:-1264828651案例#10:44214501611

很抱歉发了这么长的帖子，但我觉得这是一个有趣的问题。

Answer 1

CPP参考包含inner_product的示例实现，如下所示：

...
value = value + *first1 * *first2;
...

内部产品涉及两种类型：

1. 累加器的类型(根据传入的初始值推断，例如0LL)
2. 要相乘的元素的类型(从数组的类型推断)

因此，在您的情况下，累加器有一个int64，但元素只有int(可能是32位数据类型)。当进行乘法运算时，乘法运算的结果将以32位的精度计算！

因此，有两个可能的溢出位置，一个在+中，另一个在*中。更改初始值可以修复累加器，但在乘法运算中仍有溢出的风险。

解决这个问题的最简单方法是将输入数组更改为int64数组，而不是int数组。在这种情况下，乘法将以64位精度完成。