zcmu1866——Sumsets

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

Sample Output

HINT

题意：给你一个数字集合，让你从这个集合中找出四个数字，让他们满足a + b + c = d，并且d是满足条件中的最大值。

解决方法：如果直接枚举，O(n^4)肯定会超时。我们可以转换一下a+b=d-c，我们先枚举d-c，然后再用二分进行求a+b。复杂度就变成了O(n^2logn)

#include<cstdio>#include<cstring>#include<algorithm>#define INF 536870919using namespace std;int a[1010];int main(){	int n;	while(~scanf("%d",&n)&&n)    {        for(int i=0;i<n;i++)            scanf("%d",&a[i]);        sort(a,a+n);//排序        int flag=0;        for(int i=n-1;i>=0;i--){            for(int j=n-1;j>=0;j--){                if(i==j)                    continue;                int cnt=a[i]-a[j];//求d-c                int l=0,r=j-1;                while(l<r)//二分求a+b                {                    if(a[l]+a[r]==cnt)                    {                        flag=1;                        PRintf("%d/n",a[i]);                        break;                    }                    else if(a[l]+a[r]<cnt)                        l++;                    else                        r--;                }                if(flag)                    break;            }            if(flag)                break;        }        if(!flag)            printf("no solution/n");    }	return 0;}