贪婪算法练习无法正常工作

Question

我正在上高中，很快就要考试了，其中一个主题是Greedy算法。我在这个练习中遇到了一个未知的问题："它是一个由N个整数组成的数组。使用Greedy算法，确定可以写成两个数组元素的乘积的最大数字"(如果有点不清楚，很抱歉，我不是英语母语者)。

现在，我想解决这个问题的方法是：找到最大的两个数字和最小的两个数(如果它们都是负数)，并根据哪个数字更大，显示两个最大值或两个最小值的乘积。

这是我写的：

#include <iostream>
using namespace std;
int a[100001],n;
int main()
{
int max1=-1000001,max2=-1000001,min1=1000001,min2=1000001,x;
cin>>n;
for (int i=1; i<=n; i++)
{
cin>>a[i];
if (a[i]>=max2)
{
if (a[i]>=max1)
{
x=max1;
max1=a[i];
max2=x;
}
else max2=a[i];
}
if (a[i]<=min2)
{
if (a[i]<=min1)
{
x=min1;
min1=a[i];
min2=x;
}
else min2=a[i];
}
}
if (n==1)
cout<<n;
else if (max1*max2>=min1*min2)
cout<<max1*max2;
else cout<<min1*min2;
return 0;
}

是的，我知道我写的方式不整洁/难看。然而，代码应该能正常工作，我用练习中提供的示例和许多不同的情况对它进行了测试。他们都给出了正确的结果。问题是编程练习网站给我的代码打了80/100分，不是因为时间，而是因为答案错误。

我已经花了两个多小时研究这个代码，但我不知道它出了什么问题。有人能指出这个缺陷吗？谢谢<3

Answer 1

问题很可能是因为乘以2个int会得到一个int。int的范围通常为-2,147,483,648 to 2,147,483,647。

例如，如果将2,147,483,647 * 2相乘，则得到-2。同样地，服用2,147,483,647 + 1会得到-2147483648。当值达到最大值时，它会通过达到尽可能低的值来处理。

要部分解决这个问题，只需要将相乘的变量中的1个强制转换为64位整数。对于现代C++来说，这将是int64_t。

if (n==1)
cout<<n;
else if (static_cast<int64_t>(max1)*max2>=static_cast<int64_t>(min1)*min2)
cout<<static_cast<int64_t>(max1)*max2;
else cout<<static_cast<int64_t>(min1)*min2;

但如果两个值都足够大，你仍然可以得到太大的数字。因此，您需要uint64_t的完整范围，即无符号版本。

因此，我们需要转换为uint64_t，但随后您会遇到另一个数字低于0的问题。因此，首先应该将min1和min2转换为等效的正数，然后强制转换为uint64_t。

uint64_t positive_min1, positive_min2;
if (min1 < 0 && min2 < 0) {
positive_min1 = min1*-1;
positive_min2 = min2*-1;
}
else {
positive_min1 = 0;
positive_min2 = 0;
}

现在你可以继续做了

if (n==1)
cout<<n;
else if (static_cast<uint64_t>(max1)*max2>=positive_min1*positive_min2)
cout<<static_cast<int64_t>(max1)*max2;
else cout<<positive_min1*positive_min2;

不需要抛出positive_min1&2，因为它已经被转换为CCD_。

由于要将max1强制转换为unsigned，因此可能应该先检查它是否不低于0。

如果有符号和无符号不是熟悉的概念，您可以在这里阅读有关这一点以及不同的数据类型。