c++ - 丑陋的数字UVA

Question

<分区>

Answer 1

您的算法几乎是正确的，但错误在于您不应在生成 1500 个数字时停止，而是在“curr”达到第 1500 个数字时停止。之所以如此，是因为并非所有“curr”之后的丑陋数字都已生成，您只能确定在任何时候都拥有“curr”之前的所有丑陋数字。另一个优化算法的建议是对“curr”之后的所有数字使用堆，这样就不需要每次都对整个数组进行排序，也根本不需要使用集合。这是我的代码:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<long long> un; //using vector because we don't know how many ugly numbers we will need to generate
//If we decide to use an array (the way you did) it is better to define it outside of main().
priority_queue<long long> nun; //priority queue used for storing the next ugly numbers
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code
int main()
{
    un.push_back(1); //adding the first ugly number
    for (int i=0;i<TARGET-1;++i)
    /*
    We have already found the first ugly number (1),
    so we only need to find TARGET-1 more.
    */
    {
        nun.push(-un[i]*2);
        nun.push(-un[i]*3);
        nun.push(-un[i]*5);
        //adding the next ugly numbers to the heap
        /*
        Adding them as negative numbers because priority_queue
        keeps the largest number on the top and we need the smallest.
        */
        while (-nun.top()==un[i])
        {
            nun.pop();
            //removing duplicates
            /*
            We can prove that we will never have more than 3 copies
            of a number in the heap and thus that this will not
            affect the performance.
            1) We will never have more than one copy of a number in un.
            2) Each number can be added to nun in 3 different ways:
            by multiplying a number form un by 2, 3 or 5.
            */
        }
        un.push_back(-nun.top());
        nun.pop();
        //adding the next ugly number to un
    }
    cout<<un[TARGET-1]<<endl;
    /*
    Indexing starts at 0 so the TARGETth number is at index TARGET-1.
    */
    return 0;
}

我的程序确实输出了 859963392，正确答案。

稍微考虑一下后，我将其归结为线性复杂度。这是代码:

#include<iostream>
#include<vector>
//#include<conio.h>
using namespace std;
vector<long long> un; //using vector because we don't know how many ugly numbers we will need to generate
//If we decide to use an array (the way you did) it is better to define it outside of main().
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code
int l2=0,l3=0,l5=0; //store the indexes of the last numbers multiplied by 2, 3 and 5 respectively
int main()
{
    un.push_back(1); //adding the first ugly number
    for (int i=0;i<TARGET-1;++i)
    /*
    We have already found the first ugly number (1),
    so we only need to find TARGET-1 more.
    */
    {
        un.push_back(min(min(un[l2]*2,un[l3]*3),un[l5]*5));
        //adding the next ugly number to un
        if (un[i+1]==un[l2]*2) //checks if 2 multiplied by the number at index l2 has been included in un, if so, increment l2
        {
            ++l2;
        }
        if (un[i+1]==un[l3]*3) //checks if 3 multiplied by the number at index l3 has been included in un, if so, increment l3
        {
            ++l3;
        }
        if (un[i+1]==un[l5]*5) //checks if 5 multiplied by the number at index l5 has been included in un, if so, increment l5
        {
            ++l5;
        }
        /*
        Basically only one of the variables l2, l3 and l5 (the one we used) will be incremented in a cycle unless we can get a number
        in more than one way, in which case incrementing more than one of them is how we avoid duplicates.
        Uncomment the commented code to observe this.
        P.S. @PaulMcKenzie I can deal without a debugger just fine.
        */
        //cerr<<i<<": "<<l2<<"("<<un[l2]*2<<") "<<l3<<"("<<un[l3]*3<<") "<<l5<<"("<<un[l5]*5<<") "<<un[i+1]<<endl;
        //getch();
    }
    cout<<un[TARGET-1]<<endl;
    /*
    Indexing starts at 0 so the TARGETth number is at index TARGET-1.
    */
    return 0;
}

第一个解决方案甚至根本不需要 vector ，因为它不使用之前的数字。所以你可以通过使用单个变量来优化它。这是这样一个实现:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
long long un; //last ugly number found
priority_queue<long long> nun; //priority queue used for storing the next ugly numbers
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code
int main()
{
    un=1; //adding the first ugly number
    for (int i=0;i<TARGET-1;++i)
    /*
    We have already found the first ugly number (1),
    so we only need to find TARGET-1 more.
    */
    {
        nun.push(-un*2);
        nun.push(-un*3);
        nun.push(-un*5);
        //adding the next ugly numbers to the heap
        /*
        Adding them as negative numbers because priority_queue
        keeps the largest number on the top and we need the smallest.
        */
        while (-nun.top()==un)
        {
            nun.pop();
            //removing duplicates
            /*
            We can prove that we will never have more than 3 copies
            of a number in the heap and thus that this will not
            affect the performance.
            1) We will never have more than one copy of a number in un.
            2) Each number can be added to nun in 3 different ways:
            by multiplying a number form un by 2, 3 or 5.
            */
        }
        un=-nun.top();
        nun.pop();
        //adding the next ugly number to un
    }
    cout<<un<<endl;
    /*
    Indexing starts at 0 so the TARGETth number is at index TARGET-1.
    */
    return 0;
}

我们还可以通过释放 l2、l3 和 l5 的最小值后面的内存来优化线性解决方案以使用更少的内存。请注意，第三个解决方案和第二个解决方案的优化版本都使用次线性内存，因为 TARGET 趋于无穷大，因为在极限情况下，几乎所有难看的数字都可以被 2、3 和 5 整除。因此每次迭代我们将每个指针移动一个(因此 un 的长度不变)或者，在堆解决方案的情况下，我们将 3 个数字添加到堆中，然后从中弹出 3 个数字堆(因此堆的大小不会改变)。事实上，通过更仔细的分析，我们可以看到内存以 TARGET^(2/3) 的方式增长。