POJ 2549 Sumsets

Sumsets

Time Limit: 1000MS Memory Limit: 65536K

Description

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 +536870911 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

Sample Output

12
no solution

思路：

a + b + c = d 可以变成 a + b = d - c，然后就是先用结构体存a, b, a + b的值以便后面的判断，然后构建一个自定义函数，需要注意的是题目要求最大的数，所以就先要排序，然后再进行遍历，然后用二分的方法找到相等的值，再去比较a, b, c, d是否相等。

#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x7fffffff;
struct NODE {
	int a;
	int b;
	int sum;
	bool friend operator < (NODE a, NODE b) {
		return a.sum < b.sum;
	} 
};
NODE node[1010 * 1010];
int n, cnt;
int a[1010];
int getnum() {
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < i; j++) {
			NODE temp;
			temp.sum = a[i] - a[j];
			int x = lower_bound(node, node + cnt, temp) - node;
			if (node[x].sum == temp.sum) {
				int a1 = node[x].a;
				int b1 = node[x].b;
				if (a1 != a[i] && a1 != a[j] && b1 != a[i] && b1 != a[j]) {
					return a[i];
				}
			}
		}
	}
	return inf;
}
int main() {
	while (scanf("%d", &n) != EOF && n) {
		for (int i = 0; i < n; i++) scanf("%d", &a[i]);
		sort(a, a + n);
		cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				node[cnt].a = a[i];
				node[cnt].b = a[j];
				node[cnt++].sum = a[i] + a[j];
			}
		}
		sort(node, node + cnt);
		int ans = getnum();
		if (ans == inf) cout << "no solution\n";
		else cout << ans << endl;
	}
	return 0;
} 

第二种方案：

#include <iostream>
#include <algorithm> 
using namespace std;
const int inf = 0x7fffffff;
int main() {
	int n;
	int a[1010];
	while (scanf("%d", &n) != EOF && n) {
		for (int i = 0; i < n; i++) scanf("%d", &a[i]);
		sort(a, a + n);
		int ans = inf;
		for (int i = n - 1; i >= 0; i--) {
			for (int j = n - 1; j >= 0; j--) {
				if (i == j) continue;
				int sum = a[i] - a[j];
				int l = 0, r = j - 1;
				while (r - l >= 1) {
					if (a[r] + a[l] == sum && a[i] != a[r] && a[l] != a[i]) {
						ans = a[i];
						break;
					} else if (a[r] + a[l] > sum) {
						r--;
					} else l++;
					
				}
				if (ans != inf) break;
			}
			if (ans != inf) break;
		}
		if (ans != inf) cout << ans << endl;
		else cout << "no solution\n";
	}
	return 0;
}