1

{1,2,3} という数の配列があり、可能な限り最小のターン数で数を等しくしたいとします。ここで、「ターン」の定義は次のとおりです。

次に、要素の 1 つの値をそのまま固定し、他のすべての数値を 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 秒です。しかし、審査員サイトによると、私のコードは 1.01 秒かかります。誰でも私を助けることができますか？

私が見る限り、入力/出力部分を最適化するために、cout/cin と比較して scanf/printf ステートメントを使用しました。しかし、他に何を改善すればよいのでしょうか?

4

5 に答える 5

4

あなたのアルゴリズムでは、最大値を期待してすべての数値を増やしています。

逆に、最大値を減らして残りの数値を残した場合、結果は同じになります (ただし、メモリ/配列操作ははるかに少なくなります)。

さらに高速化するには、メモリ操作を完全に取り除くことができます ( Ivaylo Strandjevも提案しているように): 最小数を見つけ、上記の (増加するのではなく数を減少させる) ことで、減少させるために必要な減少量がわかります。すべての数をこの最小数にします。したがって、最小値を見つけたら、ターン数を計算するために 1 つのループが必要です。

あなたの例を見てください{1,2,3}

  • 最小値は 1 です
  • ターン数: (1-1)+(2-1)+(3-1) = 0 + 1 + 2 = 3

あなたが本当に賢いなら、数字を入力して現在の最小数を追跡するときに直接ターン数を計算することが可能です...試してみてください! ;)

于 2013-01-14T15:59:16.523 に答える
2

実行する必要のある実際のアクションではなく、カウントだけを気にします。したがって、移動を1つずつ実行するのではなく、実行せずに移動の数をカウントする方法を見つけてください。あなたが書いたコードは、それをどれだけうまく最適化しても、制限時間内に渡されません。あなたが行った最大の要素の観察は、途中であなたを助けます。

于 2013-01-14T15:51:42.170 に答える
1

他のコメントに加えて、私がこれを正しく理解し、コードが少し遅すぎる場合は、次の 2 つの最適化が役立ちます。

まず、 equality() と findMax() を組み合わせて、現在の最悪のケース (2 回) ではなく、配列を 1 回だけスキャンすることができます。

次に、「増加」ループを 2 つの部分 (最大位置の下と上) に分割できます。これにより、ループ内の位置を確認する手間が省けます。

于 2013-01-14T16:06:04.913 に答える
0

1) ループを展開してみる 2) SIMD 命令は使えるか？それは本当にこのコードをスピードアップします

于 2013-01-14T16:02:04.767 に答える
0

これはprintfI/O 操作であり、計算よりもはるかに遅いため、別のスレッドで行います。

また、0 から last までの順序番号を渡すだけなので、Producer-Consumer キューなどの複雑な管理も必要ありません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
        }
    }

の前にスレッドを開きscanf("%d",&t);(この初期化時間はカウントされないと思います)、isExit = true;から戻る前までにスレッドを閉じますMain()。

于 2013-01-14T16:45:11.117 に答える