UVa 10125 Sumsets (折半枚举&二分查找)

10125 - Sumsets

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1066

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

Input

Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and [phone] inclusive. The last line of input contains 0.

Output

For each S, a single line containing d, or a single line containing "no solution".

Sample Input

5
2 
3 
5 
7 
12
5
2 
16 
64 
256 
1024
0

Output for Sample Input

12
no solution

思路见代码注释。

复杂度：O(n^2 log n)

/*0.072s*/

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int a, b, sum; ///注意已经保证了a<b;
	bool operator < (const node& a) const
	{
		return sum < a.sum;
	}
} sum[499505], tmpsum;
int a[1005], tmp[4], n, c, ans, low, upp;

inline bool notequal()///判断这4个数是否互不相同
{
    int i,j;
	for (i = 0; i < 3; ++i)
		for (j = i + 1; j < 4; ++j)
			if (tmp[i] == tmp[j]) return false;
	return true;
}

bool solve()
{
    int i,j,k;
	for (i = n - 1; i >= 0; --i)///从S中最大的枚举d
		for (j = 0; j < n; ++j)///枚举c
		{
			if (j == i) continue;
			tmp[0] = a[i], tmp[1] = a[j];///a[i]是d，a[j]是c
			tmpsum = (node){a[i], a[j], a[i] - a[j]};///d-c
			low = lower_bound(sum, sum + c, tmpsum) - sum, upp = upper_bound(sum, sum + c, tmpsum) - sum;///二分找d-c
			for (k = low; k < upp; ++k)
			{
				tmp[2] = sum[k].a, tmp[3] = sum[k].b;///a和b
				if (notequal())
				{
					ans = a[i];
					return true;
				}
			}
		}
	return false;
}

int main()
{
    int i,j;
	while (scanf("%d", &n), n)
	{
		for (i = 0; i < n; ++i) scanf("%d", &a[i]);
		if (n < 4)
		{
			puts("no solution");
			continue;
		}
		sort(a, a + n);
		c = 0;
		for (i = 0; i < n - 1; ++i)
			for (j = i + 1; j < n; ++j)
				sum[c++] = (node){a[i], a[j], a[i] + a[j]};///枚举S中任意两个元素之和，并排序
		sort(sum, sum + c);
		if (solve()) printf("%d\n", ans);
		else puts("no solution");
	}
	return 0;
}

一个更快的算法：（调整法）

/*0.019s*/

#include<bits/stdc++.h>
using namespace std;

int num[1005];
int answer, a, b, c, d, n, i;

bool find()
{
	for (a = n - 1; a >= 0; --a)
	{
		for (b = n - 1; b > 1; --b)
		{
			if (a == b)	continue;
			answer = num[a] - num[b];
			for (c = 0, d = b - 1; c < d;)
			{
				if (num[c] + num[d] == answer) return true;
				else if (num[c] + num[d] < answer) ++c;
				else --d;
			}
		}
	}
	return false;
}

int main()
{
	while (scanf("%d", &n), n)
	{
		for (i = 0; i < n; ++i) scanf("%d", &num[i]);
		sort(num, num + n);
		if (find()) printf("%d\n", num[a]);
		else puts("no solution");
	}
	return 0;
}