c - TLE 至 酒店 (spoj)

Question

很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它， visit the help center 。

已关闭 11 年前。

我正在做一个 spoj 问题，我尝试这样做，但总是得到 TLE(时间限制已过期)问题是Hotels 。这是我的代码，请告诉我如何优化它。

#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 ，这五个是 2 1 3 4 5 来组成 12 那么我喜欢这样:首先我将 12 与 2 进行比较，然后是 2+1 ，然后是 2+1+3 等等，在它到达 5 后，它将 12 与 1 、 1+3 、 1+3+4 进行比较 .. 这样我就采取了只有当我发现等于 12 时才连续并中断，否则它会一直持续到最后。

希特什

Answer 1

正如您在解释中所说，无需重新启动在到达 5 后，它会将 12 与 1 、 1+3 、 1+3+4 .. 进行比较。仔细看看你的方法，你正在一次又一次地重新计算子数组的总和。例如 - 当您执行 2+1+3+4 时，您已经计算了子数组 1+3+4 的总和。因此仍有一定的优化空间。

在告诉你具体的解决方案之前，我希望你先尝试一下。另外，作为另一个提示，请参阅以下问题 Find subarray with given sum .

编辑:共享完整的解决方案以供将来使用。

#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;
}