UVa:10125 Sumsets

가장 생각 하기 쉬 운 방법 은 네 개의 수 를 매 거 하 는 것 이 니 당연히 시간 을 초과 할 것 이다.그래서 하나의 방법 이 생각 났 다. S = a + b + c, 세 개의 순환 + 2 분 으로 S 를 찾 았 고 결과 도 시간 을 초과 했다.그리고 비범 한 상상력 을 발휘 할 때 가 왔 습 니 다. S - a = b + c, 두 순환 + 2 점 에서 b + c 를 찾 습 니 다.이렇게 하면 시간의 복잡 도 를 크게 낮 출 수 있다.
b + c 의 합 을 매 거 할 수 있 습 니 다. n * (n + 1) / 2 가지 상황 이 있 을 수 있 으 므 로 배열 을 크게 해 야 합 니 다.또한 S, a, b, c 를 고려 해 야 하기 때문에 구조 체 로 b, c 의 번호 도 동시에 저장 해 야 한다.
그리고 2 점 찾기 전에 정렬 해 야 합 니 다.여기 서 가장 큰 S 를 요구 하기 때문에 먼저 이 집합 을 정렬 할 수 있 습 니 다. 마지막 으로 큰 것 부터 작은 것 까지 S 와 a 가 나타 나 면 첫 번 째 로 맞 는 S 와 a 가 답 입 니 다.
 

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct Sum_two
{
    int a,b;
    int val;
};
int BSsearch(Sum_two *A,int low,int high,int key)
{
    while(low<high)
    {
        int mid=(high+low)/2;
        if(A[mid].val==key) return mid;
        else if(key<A[mid].val) high=mid-1;
        else low=mid+1;
    }
    return -1;
}
bool cmp(Sum_two a,Sum_two b)
{
    return a.val<b.val;
}
Sum_two sum[500505];
int main()
{
    int n;
    while(scanf("%d",&n)&&n)
    {
        int a[1005]={0},ans=0;
        bool p=false;
        for(int i=0;i<n;++i)
        scanf("%d",&a[i]);
        if(n>=4)
        {
        sort(a,a+n);
        int N=0;
        for(int i=0;i<n-1;++i)
         for(int j=i+1;j<n;++j)
         {
             sum[N].val=a[i]+a[j];
             sum[N].a=i;sum[N].b=j;
             N++;
         }
         sort(sum,sum+N,cmp);
         for(int i=n-1;i>=0&&!p;--i)
          for(int j=n-1;j>=0&&!p;--j)
          {
               int key=a[i]-a[j];
               int x;
              if(i!=j&&(x=BSsearch(sum,0,N,key))!=-1)
              {
                  if(sum[x].a==i||sum[x].b==j) continue;
                  if(sum[x].a==j||sum[x].b==i) continue;
                  ans=a[i];
                  p=true;
              }
          }
        }
        if(p) printf("%d
",ans);
        else printf("no solution
");
    }
    return 0;
}