-3

私はspojの問題をやっていますが、それをやろうとしましたが、常にTLE（期限が切れています）を取得しています。質問はホテルです。これは私のコードです。最適化する方法を教えてください。

#include<stdio.h>

int main()
{
    unsigned long long int a,b,i;
    scanf("%llu %llu",&a,&b);
    unsigned long long int arr[a];
    for(i=0;i<a;i++)
    {
        scanf("%llu",&arr[i]);
    }


        unsigned long long int d;
        unsigned long long int k,z=0;
    for(i=0;i<a;i++)
    {
        d = arr[i];
        for(k=i+1;k<a+1;k++)
        {
            if (d<b)
            {
                if(z<d)
                z = d;
            }
            else
            if(d==b)
            {
                z = d;
                break;
            }
            else
            break;
            d = d + arr[k];
        }
        if(d==b)
        break;
    }
    printf("%llu",z);
    return 0;
}

このように、入力5 12の場合、これらの5つは2 1 3 4 5で12になり、次のようになります。最初に12を2と比較し、次に2 + 1、次に2 + 1+3というように続けます。 5 12対1、1 + 3、1 + 3 + 4 ..を比較します。このように、私は連続してのみ取得し、12に等しい場合は中断し、それ以外の場合は最後まで続きます。

Hitesh

4

1 に答える 1

3

説明で述べたように、再起動する必要はありませんafter it goes to 5 it compares 12 to 1 , 1+3 , 1+3+4 .. and in this way。アプローチを注意深く見てください。サブアレイの合計を何度も再計算しています。たとえば、-を1+3+4実行しているときに、サブアレイの合計をすでに計算してい2+1+3+4ます。したがって、まだある程度の最適化の余地があります。

正確な解決策を説明する前に、まず試してみてください。また、もう1つのヒントとして、次の問題を参照してください。指定された合計でサブ配列を検索します。

編集：将来の目的のために完全なソリューションを共有します。

#include<stdio.h>

/* Returns the maximum possible sum less than or equal to the gieven sum */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of first element
     and starting point as 0 */
    int curr_sum = arr[0], max_sum = 0, start = 0, i;

    /* Add elements one by one to curr_sum and if the curr_sum exceeds the
     sum, then remove starting element */
    for (i = 1; i <= n; i++)
    {
        // If curr_sum exceeds the sum, then remove the starting elements
        while (curr_sum > sum && start < i-1)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }

        //keep track of the maximum sum so far.
        if (max_sum < curr_sum)
            max_sum = curr_sum;

        curr_sum = curr_sum + arr[i];
    }

    return max_sum;
}

//上記の関数をテストするためのドライバプログラム

int main()
{
    int arr[] = {7, 3, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 9;
    printf("Max Sum = %d\n", subArraySum(arr, n, sum));
    return 0;
}
于 2012-06-03T06:07:44.407 に答える