题意:给A,B,C,D四组长度相同为n的数组,在每个数组中分别找一个数a,b,c,d使得 a+b+c+d=0。问一共有多少组这样的数据?
做法:将A和B左右数组排列相加的所有情况并放入vector1中,C和D的也按上述方式放 入vector2中。在v1中用二分查找所有和v2中元素相加为0的数。
代码:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int n;
vector <int> va,vb,vc,vd,v1,v2,v3;int main()
{int n;int x1,x2,x3,x4,tot=0;int i,j;cin>>n;for(i=0;i<n;i++){cin>>x1>>x2>>x3>>x4;va.push_back(x1),vb.push_back(x2),vc.push_back(x3),vd.push_back(x4);}for(i=0;i<n;i++)for(j=0;j<n;j++)v1.push_back(va[i]+vb[j]);for(i=0;i<n;i++)for(j=0;j<n;j++)v2.push_back(vc[i]+vd[j]);sort(v1.begin(),v1.end());sort(v2.begin(),v2.end());for(i=0;i<n*n;i++){if(binary_search(v2.begin(),v2.end(),-v1[i]))tot=tot+upper_bound(v2.begin(),v2.end(),-v1[i])-lower_bound(v2.begin(),v2.end(),-v1[i]);}cout<<tot<<endl;return 0;
}
错误原因:1 超时 用枚举法会超时;
2 WA 每次tot增加,必须是
upper_bound(v2.begin(),v2.end(),-v1[i])-lower_bound(v2.begin(),v2.end(),-v1[i])
而不是 if(bound_search(<span style="font-family: 'Microsoft YaHei';">v2.begin(),v2.end(),-v1[i])</span>))tot++;