一道很普通的搜索题目，但是必须剪枝，否则会超时
if(value!=w[i] && value!=w[j] && value!=w[k])
如果没有这句剪枝就会超时……
剪枝很强大～
1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 long w[1000];
7
8 int compare (const void * a, const void * b)
9 {
10 return ( *(int*)a - *(int*)b );
11 }
12
13 int main()
14 {
15 int N;
16 while (cin >> N && N!=0)
17 {
18 int found = false;
19
20 if (N<4)
21 {
22 cout << "no solution" << endl ;
23 continue ;
24 }
25 for (int i = 0; i < N; i++)
26 cin >> w[i];
27
28 qsort(w,(size_t)N,sizeof(long),compare);
29
30 for (int i = N - 1; i >=0; i--)
31 {
32 for (int k = N - 1; k >=0; k--)
33 {
34 if (i == k) continue;
35 for (int j = k - 1; j >=0; j--)
36 {
37 if (j == i) continue;
38 long value = w[i] - w[j] - w[k];
39 if(value!=w[i] && value!=w[j] && value!=w[k])
40 {
41 int mid ;
42 int beg = 0;
43 int end = N - 1;
44 bool searchfound = false;
45 while ( beg <= end )
46 {
47 mid = ( beg + end ) / 2 ;
48 if ( w[mid] > value )
49 end = mid-1 ;
50 else if ( w[mid] < value )
51 beg = mid+1 ;
52 else
53 {
54 searchfound = true;
55 break;
56 }
57 }
58 if (searchfound==true)
59 {
60 cout << w[i] << endl;
61 found = true;
62 goto out;
63 }
64 }
65 }
66 }
67 }
68 out:if (!found)
69 cout << "no solution" << endl;
70 }
71 return 0;
72 }