CONNECT SULFUR.....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 不正确。

Update: 试过SPOJ录用，发现map不够快，改成二分查找，录用了

我的accepted code

Answer 2

请不要使用 Map，因为它的最坏情况复杂度可以是 O(log(n)) 。

所以你可以只使用两个排序的数组和每个元素，如

第一个数组，在第二个累积数组中二进制搜索其 -ve 代理。

只需将最后几行中的查找方法更改为二进制搜索(c.begin(),c.end(),key) 并使用该索引找到重复项直到最后，因为它给出了 lower_bound索引。

总和给出了答案，它的预期复杂度是

O(n^2log(n)).

CONNECT SULFUR.....TLE 在测试用例 9 上

SPOJ SUMFOUR.....TLE on test case 9

c++

c

algorithm

c++11

maps

CONNECT SULFUR.​​....TLE 在测试用例 9 上

SPOJ SUMFOUR.....TLE on test case 9

c++

c

algorithm

c++11

maps

CONNECT SULFUR.....TLE 在测试用例 9 上