题意

给定整数集合S，求最大的d使a + b + c = d，其中a, b, c和d是S的不同元素。

Input

多case，每一行包含整数1 <= n <= 1000，表示S中的元素数，后面是S的元素，每行一个。S的每个元素都是-536870912到+536870911(含)之间的独立整数。输入的最后一行包含0。

output

输出d或“ no solution”

Sample Input

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

Sample Output

12
no solution

题解

将等式变化为 $a + b = d – c$，两重循环计算出等式左边$a+b$和并排序，将结果保存在sum数组中。

然后从大到小枚举$d$,两重循环计算处$d-c$的值，在sum数组中二分查找与$d-c$相等的$a+b$的值，时间复杂度是$O(n^2logn^2)$：

注意：$a，b，c，d$各不相同

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
#define fi first
#define se second
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef long long LL;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=1010;
struct Node
{
    int i,j;
    int s;
    bool operator<(const Node &W) const
    {
        return s<W.s;
    }
}sum[N*N];
int a[N];
int n;

bool cmp1(Node a,int b)
{
    return a.s<b;// 找到第一个>=b的结构体元素
}

bool cmp2(Node a,int b)
{
    return a.s<=b;// 找到第一个>=b的结构体元素
}

inline bool check(int a,int b,int c,int d)
{
    if(c != a && c != b && d != a && d != b) return true;
    return false;
}

int main()
{
    while(~scanf("%d",&n) && n)
    {
        for(int i=0;i<n;i++) cin>>a[i];

        sort(a,a+n);

        int cnt=0;
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                if(a[i] != a[j])
                {
                    sum[cnt].i=i;
                    sum[cnt].j=j;
                    sum[cnt].s=a[i]+a[j];
                    cnt++;
                }

        sort(sum,sum+cnt);

        bool ok=0;
        int ans=-1;
        for(int i=n-1;i>=0;i--)//从大到小枚举d
        {
            for(int j=i-1;j>=0;j--)//枚举c
            {
                if(a[i] != a[j])
                {
                    int t=a[i]-a[j];
                    Node *p1=lower_bound(sum,sum+cnt,t,cmp1);
                    Node *p2=lower_bound(sum,sum+cnt,t,cmp2);

                    if(p2-p1>0)
                        while(p1!=p2)
                        {
                            if(check(a[p1->i],a[p1->j],a[i],a[j]))
                            {
                                ok=true;
                                ans=a[i];
                                break;
                            }
                            p1++;
                        }
                }
                if(ok) break;
            }
            if(ok) break;
        }

        if(ok) cout<<ans<<endl;
        else puts("no solution");
    }
   // system("pause");
}