uva 10125

题意：

输入n，然后输入n个数字，，要在这n个数字中找出a，b，c，d。。满足a，b，c，d是不同元素，并且a + b + c = d。。。求出最大的d

直接暴力时间复杂度为O（n^4)。。会超时。。所以需要一定技巧性的枚举

原式转换成a + b = d - c；

把n个数字从小到大排列。

由于d要求最大。所以从最大开始枚举。遇到符合条件就结束。

先枚举d和c。从最大开始枚举。。每次得到一个数d-c。。

然后枚举a和b。。a从最小开始。。b从最大（由于元素不能相同。所以从c - 1）开始枚举。。

因为a往上找肯定比a大， b往下找肯定比a小。

如果a + b < d - c，a就往上找

反之。b就往下找。直到满足条件就结束。。。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int a, b, c, d, n, ans, s[1005], flag;
 9     while(scanf("%d", &n) != EOF && n)
10     {
11         for(int i = 0; i < n; i++)
12             scanf("%d", &s[i]);
13 
14         flag = 0;
15         sort(s, s+n);
16         for(d = n - 1; d >= 0; d--)
17         {
18             for(c = n - 1; c > 0; c--)
19             {
20                 if(s[c] != s[d])
21                 {
22                     ans = s[d] - s[c];
23                 }
24                 for(a = 0, b = c-1; a < b; )
25                 {
26                     if(ans == s[a] + s[b])
27                     {
28                         flag = 1;
29                         break;
30                     }
31                     else if(s[a] + s[b] < ans) a ++;
32                     else b --;
33                 }
34                 if(flag) break;
35             }
36             if(flag) break;
37         }
38         if(flag) printf("%d
", s[d]);
39         else printf("no solution
");
40     }
41 
42     return 0;
43 }

or:

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 int num[1005];
 7 int ans, a, b, c, d, n, i;
 8 
 9 bool find()
10 {
11     for(a = n - 1; a >= 0; --a)
12     {
13         for (b = n - 1; b > 1; --b)
14         {
15             if(a == b) continue;
16             ans = num[a] - num[b];
17             for (c = 0, d = b - 1; c < d; )
18             {
19                 if(num[c] + num[d] == ans) return true;
20                 else if( num[c] + num[d] < ans) ++c;
21                 else --d;
22             }
23         }
24     }
25     return false;
26 }
27 
28 int main()
29 {
30     while(scanf("%d", &n), n)
31     {
32         for(i = 0; i < n; ++i) scanf("%d", &num[i]);
33         sort(num, num + n);
34         if(find()) printf("%d
", num[a]);
35         else puts("no solution");
36     }
37 }