题意：给出四列数，要求从每一列中选择一个使得最终四个数的和为0，求有多少种情况。
分析：直接枚举的复杂度是O（n^4) 明显TL ，用二分进行简化的话是O（n^2) 。首先枚举前两列的和，然后再从后两列中查找和为前两列和的结果就可以了，因为在后两列中可能会在相同列中会出现相同的数，排完序后用upper_bound和lower_bound可以轻松求出（这样又简化了时间）。
收获：第一次接触二分查找的题目，
枚举超时的时候，试试二分能不能简化。对于大于三重的枚举来说一般都可以二分简化复杂度。
upper_bound会在数组中找到这个数最大能插入的位置；
lower_bound会在数组中找到这个数最小能插入的位置；
两者相减正好是排好序之后的数组中某个元素的个数（双击666）
#include <iostream> #include <algorithm> using namespace std; int a[4500]; int b[4500]; int c[4500]; int d[4500]; int e[4500*4500]; int main () { int k; cin >> k; for(int i=0;i<k;i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; } int z=0; for(int i=0;i<k;i++) { for(int j=0;j<k;j++) { e[z++]=a[i]+b[j]; } } sort(e,e+z); int sum = 0; for(int i=0;i<k;i++) { for(int j=0;j<k;j++) { int num=c[i]+d[j]; sum += upper_bound(e,e+z,-num)-lower_bound(e,e+z,-num); } } cout << sum << endl; }
