c++ - SPOJ SUMFOUR.....TLE 在测试用例 9 上

Question

我正在尝试解决 SPOJ 问题 SUMFOUR....我在测试用例 9 上遇到 TLE http://www.spoj.com/problems/SUMFOUR/

那么，我的代码的哪一部分必须编辑，如何编辑？这里 N<=4000

#include <iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<vector>

using namespace std;


int main()
{
int a[4005][5],n;
cin>>n;
for(int i=1;i<=n;i++)
    for(int j=1;j<=4;j++)
        scanf("%d",&a[i][j]);
int k=0;
for(int i=1;i<=n;i++)
{   int p=a[i][1];
    for(int j=1;j<=n;j++)
    {   b.push_back(p+a[j][2]);
        k++;
    }
}
k=0;
for(int i=1;i<=n;i++)
{   int p=a[i][3];
    for(int j=1;j<=n;j++)
    {   c.push_back(p+a[j][4]);
        k++;
    }
}
sort(b.begin(),b.end());
int cnt=0;
for(int j=0;j<k;j++)
    if(find(b.begin(),b.end(),-c[j])!=b.end() )
        cnt=cnt+count(b.begin(),b.end(),-c[j]) ;


printf("%d\n",cnt);
return 0;
}

Answer 1

问题出在这里:

 for(int j=0;j<k;j++)
       if(find(b.begin(),b.end(),-c[j])!=b.end() )
           cnt=cnt+count(b.begin(),b.end(),-c[j]) ;

对于 n = 4000，所以 b 和 c 中有 4000^2 个元素。所以，这个循环的时间复杂度是 4000^4，因为 find 和 count 的时间复杂度是 O(n)，这当然会导致你超过时间限制。

那么，如何才能减少时间呢？您可以使用二进制搜索 来加快计数过程，这将上述循环的时间复杂度降低到 O(n^2 log n)，正如我注意到您已经排序b.

或者，您可以使用 map统计并存储b和c中每个元素出现的频率。

map<long long, int> b;
map<long long, int> c;

for(int i=1;i<=n;i++)
{   long long p=a[i][1];
    for(int j=1;j<=n;j++)
    {   
        long long tmp =p + a[j][2];
        b[tmp] = b[tmp] + 1; 
    }
}
// Similar for c
map <long long, int>::iterator it;
long long result;
for (it = c.begin(); it != c.end(); ++it)
        result += c[it->first]*b[-(it->first)];

对于您的新更新，请更改此:

    for(int j=1;j<=n;j++)
    {   if( b.count(a[i][1]+a[j][2]) )
        {   b[a[i][1]+a[j][2]]+=1;
            c[a[i][3]+a[j][4]]+=1;
        }
        else
        {   b[a[i][1]+a[j][2]]=1;
            c[a[i][3]+a[j][4]]=1;
        } 
    }

进入这个:

    for(int j=1;j<=n;j++)
    {   
           b[a[i][1]+a[j][2]]+=1;
           c[a[i][3]+a[j][4]]+=1;            
    }

条件检查 if( b.count(a[i][1]+a[j][2]) ) 仅适用于 b，您将它用于 c，这会使 c 不正确。

更新:尝试在SPOJ中接受后，发现map不够快，所以我改成二分查找，并接受了。

我的 accepted code