ACM刷题之路（十七）二分 2019暑期集训 POJ2785

刺骨的言语ヽ痛彻心扉 2024-02-19 20:34 68阅读 0赞

4 Values whose Sum is 0

--------------------

题目链接：[传送门][Link 1]

暑期集训第一弹：**二分、三分、尺取**

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

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;
    }

[Link 1]: http://poj.org/problem?id=2785