Sumsets（4sum问题）-蒲公英云

Sumsets（4sum问题）

梦里梦外; 2022-08-01 18:06 258阅读 0赞

Sumsets

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 8954		Accepted: 2465

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

12
no solution

Source

Waterloo local 2001.06.02

这里是4sum问题或者说3sum问题求和（和是变量多了一重循

环）

正常是四重循环，这样做一定会超时的！

这里用的是三重循环，其中第三重循环是用2sum问题实现的！

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int a[1005];
int main()
{
    int n,i,j,t,l,r,flag;
    while(cin>>n&&n)
    {
        for(i=0;i<n;i++)
        {
            cin>>a[i];
        }
        sort(a,a+n);
        flag=0;
        for(i=n-1;i>=0;i--)
        {
            for(j=n-1;j>=0;j--)
            {
                if(i!=j)
                {
                    t=a[i]-a[j];
                    for(l=0,r=j-1;l<r;)
                    {
                        if(a[l]+a[r]==t)
                        {
                            flag=1;
                            break;
                        }
                        else if(a[l]+a[r]>t)
                        {
                            r--;
                        }
                        else
                        {
                            l++;
                        }
                    }
                    if(flag)
                    {
                        break;
                    }
                }
            }
            if(flag)
            {
                break;
            }
        }
        if(flag)
        {
            cout<<a[i]<<endl;
        }
        else
        {
            cout<<"no solution"<<endl;
        }
    }
}