4数列选数问题

四数列选数问题

问题描述

有四个数列 A, B, C, D，每个数列都有 n 个数字。从每个数列中各取出一个数，有多少种方案使得 4 个数的和为 0 ？
(当一个数列中有多个相同的数字的时候，把它们当做不同的数对待。)

Input

第一行：n (代表数列中数字的个数) (1 ≤ n ≤ 4000)
接下来的 n 行中，第 i 行有四个数字，分别表示数列 A, B, C, D 中的第 i 个数字 (数字不超过 2 的 28 次方)

Output

输出不同组合的个数。

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
Output: 
5

Limitation

Time limit		15000 ms
Case time limit	5000 ms
Memory limit	228000 kB

解题思路

有4个数列，用4重for循环暴力求解的话，时间复杂度为O(n⁴)，一定会超时，所以要进行优化。

题意很明显求和为0，两个相反数相加为0，因此可以把4个数列优化成2个数列：A和B、C和D依次通过 n² 次相加得到数列 E(A和B产生)和 F(C和D产生)，然后对F中的每一个数求相反数，A再从新F中找到相同的数即可。时间复杂度优化为O(n²)。

优化查找效率：二分搜索。
标记始末，求得中间，把中间数与目标对比，大则将末改成中间-1，小则将始改成中间+1，循环搜索，直至始末相遇或找到目标。
这道题要标记的是有序数组中目标出现的第一个位置，然后从那个位置开始求多少个相同值，就表示有多少个方案，再对这些方案数求和就是答案。

源代码

#include <iostream>
#include <algorithm>
using namespace std;

/*二分查找 是否存在那个数
  从两端开始往目标逼近*/
bool findNum(int x, int* a, int n) {
	int first = 0, last = n - 1, middle;
	bool found = false;
	while (!found && first <= last) {
		middle = (first + last) / 2;
		if (a[middle] == x)
			found = true;
		if (a[middle] > x)
			last = middle - 1;
		if (a[middle] < x)
			first = middle + 1;
	}
	return found;
}
/*找到那个数第一次出现的位置*/
int findFirst(int x, int* a, int n) {
	int first = 0, last = n - 1, middle;
	while (first < last) {
		middle = (first + last) / 2;
		if (a[middle] < x)
			first = middle + 1;
		else
			last = middle;
	}
	return first;
}
/*其实上面两个二分搜索可以合并成一个的……
  就是后来懒得改了……*/

/*从那个数的位置开始 计算那个数在有序数组中出现了几次*/
int CountNum(int pos, int x, int* a, int n) {
	int count = 0;
	for (int i = pos; i < n; i++) {
		if (a[i] != x)
			break;//及时停止
		count++;
	}
	return count;
}

int main() {
	int n;
	cin >> n;
	int* arr1 = new int[n + 10];//A
	int* arr2 = new int[n + 10];//B
	int* arr3 = new int[n + 10];//C
	int* arr4 = new int[n + 10];//D
	for (int i = 0; i < n; i++) {
		cin >> arr1[i];
		cin >> arr2[i];
		cin >> arr3[i];
		cin >> arr4[i];
	}
	int* a1 = new int[n * n + 10];//A和B → E
	int* a2 = new int[n * n + 10];//C和D → F
	int count = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			a1[count] = arr1[i] + arr2[j];
			a2[count] = (-1) * (arr3[i] + arr4[j]);//这边直接求相反数
			count++;
		}
	}

	sort(a2, a2 + n * n);//要先进行排序

	int numCount = 0;
	for (int i = 0; i < n * n; i++) {//遍历
		if (findNum(a1[i], a2, n * n) == true) {//如果有
			int first = findFirst(a1[i], a2, n * n);//找到第一次出现的位置
			numCount += CountNum(first, a1[i], a2, n * n);//计数 出现几次 求和
		}
	}
	cout << numCount << endl;

	return 0;
}