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
6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45Sample Output
5Hint
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函数，功能在本题中一样
基础二分题，主要采用了用空间换时间的思想
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
inline bool scan_d(int& num)//输入挂
{
char in; bool IsN = false;
in = getchar();
if (in == EOF) return false;
while (in != '-' && (in<'0' || in>'9')) in = getchar();
if (in == '-') { IsN = true; num = 0; }
else num = in - '0';
while (in = getchar(), in >= '0' && in <= '9')
{
num *= 10, num += in - '0';
}
if (IsN) num = -num;
return true;
}
int main()
{
int n;
scanf_s("%d", &n);
vector<int>v[5];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 4; j++) {
int num;
scanf_s("%d", &num);
v[j].push_back(num);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
v[4].push_back(v[2][i] + v[3][j]);//把第三列第四列合并放入v[4]
}
}
int cnt = 0;
sort(v[4].begin(), v[4].end());
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; ++j)
{
int ans = 0 - v[0][i] - v[1][j];//真正需要的值
int index = lower_bound(v[4].begin(), v[4].end(), ans) - v[4].begin();
//index找大于等于ans的首位置 下行同理
if (lower_bound(v[4].begin(), v[4].end(), ans) != v[4].end() && v[4][index] == ans)
{//该函数找不到返回end()； cnt加上找到该值的数量
int indexx = lower_bound(v[4].begin(), v[4].end(), ans + 1) - v[4].begin();
cnt += indexx - index;
}
}
}
printf("%d
", cnt);
return 0;
}