c++ - 贪婪算法练习无法正常工作

我正在上高中，不久就要进行测试，其中一个主题是贪婪算法。我在此练习中遇到一个未知的问题：“给了它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分，这不是因为时间短，而是因为答案错误。

我已经花了两个多小时来查看这段代码，但我只是想不出这是怎么回事。谁能指出这个缺陷？谢谢

最佳答案

问题很可能是由于将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;

由于它已经转换为uint64_t，因此无需强制转换positive_min1＆2。

由于您将max1强制转换为无符号，因此您可能应该首先检查它是否不小于0。

如果不熟悉带符号和无符号的概念，则可以阅读有关此信息以及不同的数据类型here的信息。