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 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函数,功能在本题中一样
基础二分题,主要采用了用空间换时间的思想
#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\n", cnt);
return 0;
}