Sumsets（4sum问题）

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

Sumsets

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 8954</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 2465</td> 
  </tr> 
 </tbody> 
</table>

Description

![2549_1.jpg][]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

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;
            }
        }
    }

[2549_1.jpg]: /images/20220731/8f0198b8b41e4a41adc43e81afbf9ea9.png
[Waterloo local 2001.06.02]: http://poj.org/searchproblem?field=source&key=Waterloo+local+2001.06.02