1

假设我们有一个数字数组 {1,2,3}，我们希望在尽可能少的圈数内使数字相等；其中“转弯”的定义如下：

反过来，您需要按原样固定其中一个元素的值，然后每隔一个数字递增 1。

考虑到例如。已经提到 - A={1,2,3} ，目标是使它们均衡。我已经做的是制定逻辑，即使用最小圈数的方法是在每圈中选择最大圈数。

迭代 1：保持 A[2]=3。迭代结束时的数组 => {2,3,3}

迭代 2：保持 A[2]=3。迭代结束时的数组 => {3,4,3}

迭代 3：保持 A[1]=4。迭代结束时的数组 => {4,4,4}

因此，转数 = 3

我写的代码如下：

#include<iostream>
#include<stdio.h>

int findMax(int *a,int n)
{
    int i,max;
    max=1;
    for(i=2;i<=n;i++)
    {
        if(a[i]>a[max])
        {
            max=i;
        }     

    }
    return max;
}

int equality(int *a,int n)
{
    int i;
    for(i=1;i<n;i++)
    {
        if(a[i]!=a[i+1]) return 0;
    }
    return 1;
}

int main()
{
    int a[100],i,count,t,posn_max,n,ip=0;
    scanf("%d",&t);
    while(ip<t)
    {
        count=0;
        scanf("%d",&n);

        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        while(equality(a,n)==0)
        {
            posn_max=findMax(a,n);

            for(i=1;i<=n;i++)
            {
                if(i!=posn_max)
                {
                    a[i]=a[i]+1;
                }
            }
            count++;

        }
        printf("%d\n",count);
        ip++;
    }
    return 0;
}

这给了我我需要的正确答案。但我想进一步优化它。

我的时间限制是 1.0 s 。但是法官网站告诉我我的代码需要 1.01 秒。谁能帮我吗？

据我所知，与 cout/cin 相比，我使用了 scanf/printf 语句，以优化输入/输出部分。但是我还应该做得更好吗？

4

5 回答 5

4

在您的算法中，您正在增加期望中的所有数字以获得最大值。

如果你反过来做，减少最大值并保留其余数字，结果应该是相同的（但内存/数组操作要少得多）！

为了使其更快，您可以完全摆脱内存操作（也正如Ivaylo Strandjev所建议的那样）：找到最小数字并通过上述想法（减少数字而不是增加）您知道需要减少多少所有数字到这个最小数字。因此，在找到最小值后，您需要一个循环来计算圈数。

以你为例{1,2,3}

  • 最小值为 1
  • 圈数：(1-1)+(2-1)+(3-1) = 0 + 1 + 2 = 3

如果你真的很聪明，可以在输入数字时直接计算圈数并跟踪当前的最小圈数……试试吧！;)

于 2013-01-14T15:59:16.523 回答
2

您只关心计数而不关心您需要执行的实际操作。因此，与其逐个执行动作，不如尝试找到一种方法来计算不执行动作的数量。你写的代码再优化也不会超过时限。您所做的最大元素观察将在此过程中为您提供帮助。

于 2013-01-14T15:51:42.170 回答
1

除了其他评论之外，如果我做对了并且您的代码有点太慢，这里有两个优化应该可以帮助您。

首先，您可以将equality() 和findMax() 结合起来，并且只扫描一次数组，而不是当前最坏的情况（两次）。

其次，您可以将“增加”循环分成两部分（低于和高于最大位置）。这将消除检查循环中位置的工作。

于 2013-01-14T16:06:04.913 回答
0

1) 尝试展开循环 2) 你可以使用 SIMD 指令吗？那真的会加快这段代码的速度

于 2013-01-14T16:02:04.767 回答
0

我会printf在一个单独的线程中，因为它是一个 I/O 操作并且比您的计算慢得多。

它也不需要复杂的管理，例如 Producer-Consumer 队列，因为您只传递从 0 到 last 的有序数字count。

这是伪代码：

    volatile int m_count = 0;
    volatile bool isExit = false;

    void ParallelPrint()
    {
        int currCount = 0;

        while (!isExit)
        {
            while (currCount < m_count)
            {
                currCount++;
                printf("%d\n", currCount);
            }

            Sleep(0); // just content switch
        }
    }

Open the thread before the scanf("%d",&t); (I guess this initialization time is not counted), and close the thread by isExit = true; before the return from your Main().

于 2013-01-14T16:45:11.117 回答