codeforces-2549【枚舉】【特殊的二分】

題目連結：​​點選打開連結​​

Sumsets

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 11104	Accepted: 3036

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 [phone] 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

52

3

5

7

12

5

2

16

64

256

1024

Sample Output

12no solution

題意：在集合 S 中有 n 個數，找到最大的 d，且 d 滿足于集合内 a+b+c=d。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=1e6+10;
int n;
int a[1010];
bool judge(int l,int r,int x) // 特殊的二分 
{
  while(l<r)
  {
    if(x<a[l]+a[r])
      r--;
    else if(x>a[l]+a[r])
      l++;
    else
      return 1;
  }
  return 0;
}
int main()
{
  while(scanf("%d",&n),n)
  {
    for(int i=0;i<n;i++)
      scanf("%d",a+i);
    sort(a,a+n);
    bool flag=0;
    for(int i=n-1;i>=0;i--)
    {
      for(int j=n-1;j>=0;j--)
      {
        if(i==j)  continue;
        if(judge(0,j-1,a[i]-a[j]))
        {
          printf("%d\n",a[i]);
          flag=1;  
          break;
        }
      }
      if(flag)  break;
    }
    if(!flag)
      puts("no solution");
  }
  return 0;
 }