首先最容易想到的是暴力的四层遍历,时间复杂度为O(n^4)。
对最后一层的遍历可以改成二分查找,时间复杂度为O(n^3logn)。
但上两种方式都会超时。
有四个数字序列,可以联想到先使用二重循环将前两个和后两个序列的所有结果求出来。
然后在根据前一个求出来的序列去二分寻找后一个序列中符合要求的有多少种。
对最后一层的遍历可以改成二分查找,时间复杂度为O(n^3logn)。
但上两种方式都会超时。
有四个数字序列,可以联想到先使用二重循环将前两个和后两个序列的所有结果求出来。
然后在根据前一个求出来的序列去二分寻找后一个序列中符合要求的有多少种。
这样的时间复杂度:O(n^2+nlogn)
//首先最容易想到的是暴力的四层遍历,时间复杂度为O(n^4)。 //对最后一层的遍历可以改成二分查找,时间复杂度为O(n^3logn)。 //但上两种方式都会超时。 //有四个数字序列,可以联想到先使用二重循环将前两个和后两个序列的所有结果求出来。 //然后在根据前一个求出来的序列去二分寻找后一个序列中符合要求的有多少种。 //这样的时间复杂度:O(n^2+nlogn) #include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn = 1000+10; int a[maxn], b[maxn], c[maxn], d[maxn]; int abn, cdn; ll ab[maxn*maxn], cd[maxn*maxn]; int main() { int n; scanf("%d", &n); for (int i=0;i<n;i++) { scanf("%d %d %d %d", a+i, b+i, c+i, d+i); } //两两计算所有的计算结果 for (int i=0;i<n;i++) { for (int j=0;j<n;j++) { ab[abn++] = a[i]+b[j]; cd[cdn++] = c[i]+d[j]; } } ll cnt = 0; //将第二个排序,以便使用二分查找 sort(cd, cd+cdn); for (int i=0;i<abn;i++) { int num = upper_bound(cd, cd+cdn, -ab[i])-lower_bound(cd, cd+cdn, -ab[i]); cnt += num; } cout<<cnt; return 0; }