4 Values whose Sum is 0
题目链接：传送门
暑期集训第一弹：二分、三分、尺取
Description
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input
1. 6 2. -45 22 42 -16 3. -41 -27 56 30 4. -36 53 -37 77 5. -36 30 -75 -46 6. 26 -38 -10 62 7. -32 -54 -6 45
Sample Output
5
Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
题意：先输入一个n，表示有n行4列的数，让你每一行选出一个数字，四个数加起来刚好是0的组合数有多少种？
注：一列中的一个元素可以被多次组合。 时限15秒
最暴力的方法：o(n^4)
每一列的数进行遍历，如果相加等于0让总计的cnt加加——超时
其次：o(n^3*logn)
对前三列遍历，对最后一列排序二分查找，如果可以找到，那么加上这个数的个数。——超时
再次：o(n^2*log (n*n) )
对前两列遍历，把第三列第四列合并成数量为n*n的数组，并对其进行二分查找，如果可以找到，那么加上这个数的个数。——AC 7219ms
最后：o(n*log (n*n*n) )
对前一列遍历，把第二列第三列第四列合并成数量为n*n*n的数组，并对其进行二分查找，如果可以找到，那么加上这个数的个数。——爆内存
所以最后AC的方法是第三种，代码如下：
其中 inline bool scan_d(int& num) 是输入挂 当输入数据较多的时候能明显减少输入耗时
inline是内联函数 C++ 对于多次调用的函数，可以使用内联，减低时间消耗，增加主函数的内存消耗。
因为用的是VS2019 ，scanf要报错，所以使用scanf_s函数，功能在本题中一样
基础二分题，主要采用了用空间换时间的思想
1. #include<iostream> 2. #include<algorithm> 3. #include<cstring> 4. #include<vector> 5. using namespace std; 6. inline bool scan_d(int& num)//输入挂 7. { 8. char in; bool IsN = false; 9. in = getchar(); 10. if (in == EOF) return false; 11. while (in != '-' && (in<'0' || in>'9')) in = getchar(); 12. if (in == '-') { IsN = true; num = 0; } 13. else num = in - '0'; 14. while (in = getchar(), in >= '0' && in <= '9') 15. { 16. num *= 10, num += in - '0'; 17. } 18. if (IsN) num = -num; 19. return true; 20. } 21. int main() 22. { 23. int n; 24. scanf_s("%d", &n); 25. vector<int>v[5]; 26. for (int i = 0; i < n; i++) 27. { 28. for (int j = 0; j < 4; j++) { 29. int num; 30. scanf_s("%d", &num); 31. v[j].push_back(num); 32. } 33. } 34. for (int i = 0; i < n; i++) { 35. for (int j = 0; j < n; j++) { 36. v[4].push_back(v[2][i] + v[3][j]);//把第三列第四列合并放入v[4] 37. } 38. } 39. int cnt = 0; 40. sort(v[4].begin(), v[4].end()); 41. for (int i = 0; i < n; i++) 42. { 43. for (int j = 0; j < n; ++j) 44. { 45. int ans = 0 - v[0][i] - v[1][j];//真正需要的值 46. int index = lower_bound(v[4].begin(), v[4].end(), ans) - v[4].begin(); 47. //index找大于等于ans的首位置 下行同理 48. if (lower_bound(v[4].begin(), v[4].end(), ans) != v[4].end() && v[4][index] == ans) 49. {//该函数找不到返回end()； cnt加上找到该值的数量 50. int indexx = lower_bound(v[4].begin(), v[4].end(), ans + 1) - v[4].begin(); 51. cnt += indexx - index; 52. } 53. } 54. } 55. printf("%d\n", cnt); 56. return 0; 57. }
