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

Question

我在读高中，马上就要考试了，其中一个主题是贪心算法。我在这个练习中遇到了一个未知的问题:“它被赋予了一个 N 个整数的数组。使用贪心算法，确定可以写成两个数组元素的乘积的最大数字”(对不起，如果它有点不清楚，我不是以英语为母语的人)。

现在，我想要解决这个练习的是:找到最大的两个数字和最小的两个数字(如果它们都是负数)并显示两个最大或两个最小的乘积，取决于哪个数字更大。

这是我写的:

#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 个多小时查看这段代码，但我无法弄清楚它有什么问题。任何人都可以指出这个缺陷吗？谢谢<3

Answer 1

问题很可能是因为 2 个整数相乘会得到一个整数。 int 通常具有 -2,147,483,648 到 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，因为它已经转换为 uint64_t。

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

如果有符号和无符号不是您熟悉的概念，您可以阅读相关内容以及不同的数据类型 here .