uva 10125 二分

和之前做过的一道a+b+c=X的问题类似，不过这个要求多了a+b+c=d-->a+b=d-c 且abcd互不相等

我们可以处理出所有的a+b的组合并记录a,b，可以保存在结构体内。

接着对x排序，倒序枚举d，对每一个d遍历除d以外的其他数当做c，对(d-c)的值在排序后的结构体数组中二分找到第一个等于这个值得位置，

接着往后遍历所有值等于(d-c)的位置，并判定a,b,c,d是否互不相等，如果是输出这个数后退出。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node
 4 {
 5  int a,b,s;
 6  bool operator<(const node& tmp)const{
 7  return s<tmp.s;
 8  }
 9 }P[1000005];
10 int x[1005];
11 bool can(int c,int d,int n)
12 {
13     int l=0,r=n-1,mid;
14     while(l<r){
15         mid=l+((r-l)>>1);
16         if(P[mid].s==x[d]-x[c]){
17             r=mid;
18         }
19         else if(P[mid].s>x[d]-x[c]){
20             r=mid-1;
21         }
22         else l=mid+1;
23     }
24     while(l<n&&P[l].s==x[d]-x[c]){
25         if(P[l].a!=c&&P[l].b!=d&&P[l].a!=d&&P[l].b!=c) return 1;
26         l++;
27     }
28     return 0;
29 }
30 int main()
31 {
32     int a,b,c,d,n,i,j;
33     while(cin>>n&&n){int p=0;
34         for(i=1;i<=n;++i)
35         {
36             scanf("%d",&x[i]);
37             for(j=1;j<i;++j)
38             {
39                P[p].a=i;
40                P[p].b=j;
41                P[p++].s=x[i]+x[j];
42             }
43         }
44         sort(P,P+p);
45         sort(x+1,x+1+n);
46         bool ok=0;
47         for(int d=n;d>=1;d--)
48         {
49             for(int c=n;c>=1;c--)
50             {
51                 if(c==d) continue;
52                 if(can(c,d,p)) {ok=1;cout<<x[d]<<endl;break;}
53             }
54             if(ok) break;
55         }
56         if(!ok) puts("no solution");
57     }
58     return 0;
59 }