10125 - Sumsets

题目：10125 - Sumsets

题目大意：从给出的数的集合中，找出里面某个值d，d = a + b+ c；（a，b， c也是属于这个集合）。要求求最大的d。

阶梯思路：把集合里的数排序，然后d从小到大的尝试， b + c = d - a。 a的话也从做大的尝试，这样能快速找到不符合的，然后 b 和c 从两头开始判断，b取最小的，c去最大的，然后如果版 b  + c

> d - a, 说明b要往前移，反之，c 就要往后移。

注意这里的每个值都有可能成为d，第一个最小的也不例外，因为有负数存在。

#include<stdio.h>
#include<algorithm>
using namespace std;

const int N = 1005;
int s[N], n;
int ans;

int find() {

	for ( int l = n - 1; l >= 0; l--) {

		for ( int i = n - 1; i > 0; i-- ) {
		
			if ( l == i)
				continue;
			int sum = s[l] - s[i], j, k;
			for (j = 0 , k = i - 1; j < k; j++, k-- ) {
			
				int temp = s[j] + s[k];
				if (temp > sum) 
					j--;
				else if (temp < sum) 	
					k++;
				else {
					ans = s[l];
					return 1;
				}
			}
	
		}
	}
	return 0;
}

int main () {

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

10125 - Sumsets,布布扣,bubuko.com

10125 - Sumsets

原文：http://blog.csdn.net/u012997373/article/details/22847581