c++ - 做对了类似竞争的问题，但在提高效率方面需要帮助

Question

问题很简单。我得到 N - 一个数字的位数，然后是一个数字的 N 位。我需要准确地进行一位数字转换并获得尽可能高的数字。我确实做对了问题（如给出了正确的数字），但它将达到 1 秒时间限制 afaik。如何提高程序的效率，使其在 N <= 10^6 的情况下受到 1 秒时间限制。堆栈溢出的新内容，所以请告诉我是否在提出问题时做错了，以便我可以修复它。谢谢。这是我的解决方案：

主要的：

int n;
cin >> n;
int a[n+1];
for(int i=0;i<n;++i)
    cin >> a[i];
int maxofarray1;
bool changeHappened=false;
bool thereAreTwoSame=false;
for(int i=0;i<n;++i) //changing the two digits to make the highest number if possible
{
    maxofarray1=maxofarray(a,i+1,n);
    if(a[i]<maxofarray1)
    {
        int temp=a[a[n]];
        a[a[n]]=a[i];
        a[i]=temp;
        changeHappened = true;
        break;
    }
}

for(int i=0;i<n;++i) //need to check if there are two of the same digit so I can change 
//those two making the number the same instead of making it lower
    for(int j=i+1;j<n;++j)
        if(a[i]==a[j])
        {
            thereAreTwoSame=true;
            break;
        }

if(!changeHappened) //if the change has not been yet made, either leaving the number as is 
//(changing two same numbers) or changing the last two to do as little "damage" to the number
{
    if(!thereAreTwoSame)
    {
        int temp=a[n-1];
        a[n-1]=a[n-2];
        a[n-2]=temp;
    }
}
for(int i=0;i<n;++i)
    cout << a[i] << " ";
return 0;

最大数组：

int maxofarray(int a[], int i,int n) //finding the maximum of the array from i to n
{
    int max1=0;
    int maxind;
    for(int j=i;j<n;++j)
    {
        if(max1<a[j])
        {
            max1=a[j];
            maxind=j;
        }
    }
    a[n]=maxind; //can't return both the index and maximum (without complicating with structs) 
    //so I add it as the last element
    return max1;
}

标签： c++optimizationtime

Answer 1

您的代码中的问题是复杂性。我没有完全理解你的算法，但是嵌套循环是一个危险信号。与其尝试改进代码的零碎部分，不如重新考虑整体策略。

让我们首先假设数字9确实出现在数字中。考虑数字是

9...9 c ...9...

9...9所有的前导数字在哪里 9（可能一个都没有）。我们不能通过交换其中一个来使数字更大。

c是第一个数字!=9，即它是我们可以放 a9以获得更大数字的地方。9是放在这个地方时将使数字最大的数字。

Last,...9...表示最后出现的数字9和与之相关的数字。之后9没有其他9人出现。虽然我们通过替换来增加数字，但替换c那个数字会变小9，因此我们必须选择最后一个。

对于一般情况，只需要稍微多一点。这是一个粗略的草图：

 std::array<size_t,10> first_non_appearance;
 std::array<size_t,10> last_appearance;

 size_t n;
 std::cin >> n;
 std::vector<int> number(n);
 for (size_t i=0;i <n;++i) {
     std::cin >> a[i];
     for (int d=0;d<10;++d) {
         // keep track of first and last appearance of each digit
     }
 }

 size_t first = 0;
 size_t second = 0;
 for (int d=0;d<10;++d) {
      // determine biggest digit that appeared and use that
 }
 std:swap( a[first],a[last] );

它不完整，可能需要处理特殊情况（例如只有一位数字的数字），但我希望它有所帮助。

PS：您使用的是可变长度数组 ( int a[n+1];)，这不是标准 C++。在 C++ 中，您应该std::vector在仅在运行时知道大小时使用 a （并且在知道大小时使用 a std::array）。