-2

我试图通过首先对向量进行排序然后将向量的最后两个元素相乘来解决最大成对乘积问题。

它适用于较小的数字，但不适用于 10^5 数字。

任何人都可以看看并提供帮助吗？

这是我的功能

long long MaxPairwiseProductFast(const vector<int> &number)
{
    long long result = 0;
    long n = number.size();
    result = number.at(n-1) * number.at(n-2);
    return result;
}

这是我的主要功能

int main()
{
    int n;
    cin>>n;
    vector<int>numbers(n);
    for(int i = 0; i <n; i++){
     cin>>numbers[i];
    }
   sort(numbers.begin(), numbers.end());

    long long result = MaxPairwiseProductFast(numbers);

    cout<<result<<"\n";

    return 0;
}

它适用于较小的范围，但即使在使用 long long 后也不适用于较大的范围

4

2 回答 2

1

首先，您需要将向量的数据类型从您写入的任何地方int更改为.long longvector<int>numbervector<long long>number

要获得正确的输出，您需要做的另一个更改是，您必须考虑至少有两个更大的负数的情况。

例如：如果向量包含 : {-10, -5, -2, 0, 1, 2}。
您的程序将输出：1 * 2 = 2作为答案。
但是，这种情况的答案将是：-10 * -5 = 50.

因此，修正后的计算方法为：

long long MaxPairwiseProductFast(const vector<long long> &number)
{
  long long result = 0;
  long n = number.size();
  if (n < 2) return 0;
  result = number.at(n-1) * number.at(n-2);
  result = max(result, number.at(0) * number.at(1));
  return result;
}
于 2019-05-02T10:07:30.337 回答
1

您不需要像其他答案所建议的那样更改所有数据类型。只需像这样修复您的乘法：

long long MaxPairwiseProductFast(const vector<int> &number)
{
    long long result = 0;
    long n = number.size();
    result = number.at(n-1) * (long long)number.at(n-2);
    return result;
}

问题是您将 2 相乘int * int，这会产生 a int，然后将其作为 a 返回long long。您需要在乘法之前转换其中一个，这样它就会long long与long long结果进行乘法运算。

正如 Bishal 建议的那样，还要检查最小两个数字的乘积，因为-5 * -5 > 4 * 4

于 2019-05-02T11:58:48.520 回答