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

Question

我在读高中，马上就要考试了，其中一个题目是贪心算法。我在这个练习中遇到了一个未知问题："It is given an array of N integers. Using the Greedy algorithm, determine the largest number that can be written as a multiplication of two of the array elements"（抱歉，如果有点不清楚，我不是以英语为母语的人）。

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

这是我写的：

#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;
}

是的，我知道我的写法是untidy/ugly。但是，该代码应该可以正常运行，并且我使用练习提供的示例和许多不同的情况对其进行了测试。他们都给出了正确的结果。问题是编程练习网站给我的代码打了80/100分，不是因为时间问题，而是因为答错了。

我已经花了 2 个多小时查看这段代码，但我无法弄清楚它有什么问题。任何人都可以指出这个缺陷吗？谢谢 <3

Answer 1

问题很可能是因为 2 个整数相乘会得到一个整数。 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 因为它已经转换为 uint64_t.

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

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

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

Greedy algorithm exercise not working properly

c++

greedy