时间限制错误在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（超过时间限制）错误，因为对此我只得到了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; 

}