c++ - CodeChef 上的时间限制错误

Question

This Is The Question

这是我的解决方案:

#include <iostream>

using namespace std;

int main(){
    unsigned long numberOfGums;
    unsigned long hardnessLimit;
    unsigned long counter = 0;

    cin >> numberOfGums;
    cin >> hardnessLimit;

    unsigned long gums[numberOfGums];

    for(unsigned long i=0; i<numberOfGums; i++){
        cin >> gums[i];
    }

    for(unsigned long i=0; i<numberOfGums; i++){
        if(gums[i] < hardnessLimit){
            for(unsigned long j=i+1; j<numberOfGums; j++){
                if((gums[i] + gums[j]) < hardnessLimit){
                    counter++;
                }
            }
        }
    }

    cout << counter << endl;

    return 0;
}

这个程序给我 TLE(Time Limit Exceeded) 错误，因此我只得到 30 分(满分 100 分)。具体来说，这个程序无法完成 子任务-2 值得剩下的 70 分(在问题页面上给出)。

我尝试过使用 printf 和 scanf 而不是 cin 和 cout，但程序仍然不够快。

我可以做些什么来改进这个程序，或者什么是解决这个问题的更好方法。

我也试过了，但得到了同样的错误:

#include <iostream>

using namespace std;

int main(){
    long numberOfGums;
    long hardnessLimit;
    long counter = 0;
    long temp = 0;

    cin >> numberOfGums;
    cin >> hardnessLimit;

    long gums[numberOfGums];

    for(long i=0; i<numberOfGums; i++){
        cin >> temp;
        if(temp < hardnessLimit){
            gums[i] = temp;
        }
    }

    for(long i=0; i<numberOfGums; i++){
        if(gums[i] != -1){
            for(long j=i+1; (j<numberOfGums); j++){
                if(((gums[i] + gums[j]) < hardnessLimit) && gums[j] != -1){
                    counter++;
                }
            }
        }
    }

    cout << counter << endl;

    return 0;
}

Answer 1

您的解决方案是 O(N^2)，它肯定会在给定约束的情况下超时。

更有效的解决方案是 O(NlogN) 解决方案。这是算法的基本轮廓:

• 对数组进行排序。这需要 O(NlogN) 时间。

• 现在对于排序数组中的每个元素，比如 p，在数组中搜索元素索引(元素 p 的右侧)，使得该索引处的值小于 k - p。为此使用二进制搜索。找到这个索引后，您可以很容易地计算出与元素 p 关联的此类对的数量。对于每个元素，此完整步骤花费 O(logN) 时间

• 对数组中除最后一个元素之外的所有元素执行上述过程，因为它的右边没有左边的数组。

您将通过对您获得的每个元素 p 的所有对求和来得到答案

希望对您有所帮助!!!

编辑:我正在添加上述算法的 C++ 实现。该解决方案通过了 CodeChef 上的所有测试用例。

#include <iostream>
#include <algorithm>
using namespace std;
int binsearch(int a[],int n, int x)
{
    int low, high, mid, k=-1;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid] <= x-1){
            k = mid;
            low = mid+1;
        }
        else{
            high = mid-1;
        }

    }
    return k;
}
int main() 
{
    int n, k, i, j;
    long long ans = 0;
    cin>>n>>k;
    int arr[n];

    for(i=0;i<n;i++)
    {
        cin>>arr[i];
    }

    sort(arr,arr+n);

    j = 0;

    while(j<n-1)
    {
        if(k-arr[j] > 0)
        {
            int ind = binsearch(arr,n,k-arr[j]);
            ans = ans + (ind-j>=0 ? (ind-j):0);
        }
        j++;
    }
    cout<<ans<<endl;
    return 0;

}