簡單題,求解序列中三個數(shù)相加最大且存在于序列中的數(shù).利用三層循環(huán)遍歷加二分搜索可在n
3*logn時間內(nèi)解決(排序用nlogn時間).
Code
1
#include <iostream>
2#include <algorithm>
3using namespace std;
4
5int IntCompare(const void * i1, const void * i2)
6
{
7
return (*(const int*)i1) > (*(const int*)i2);
8
}
9
10int _tmain(int argc, _TCHAR* argv[])
11{
12 int * gamblers, n;
13 while(cin >> n && n != 0)
14
{
15 int firstResult, secondResult;
16 bool isFind = false;
17 gamblers = new int[n];
18 for(int i = 0; i < n; ++i)
19 {
20 cin >> gamblers[i];
21
}
22
23 qsort(gamblers, n, sizeof(int), IntCompare);
24
25 for(int i = n - 1; i >= 0; --i)
26 {
27 for(int j = 0; j < n; ++j)
28 {
29 if(j == i)
30 continue;
31 firstResult = gamblers[i] - gamblers[j];
32 for(int k = 0; k < n; ++k)
33 {
34 if(k == i || k == j)
35 continue;
36 secondResult = firstResult - gamblers[k];
37
38 if(secondResult == gamblers[i]
39 || secondResult == gamblers[j]
40 || secondResult == gamblers[k])
41 continue;
42
43 if(binary_search(gamblers, gamblers + n, secondResult))
44 {
45 cout << gamblers[i] << endl;
46 isFind = true;
47 break;
48 }
49 }
50 if(isFind)
51 break;
52 }
53 if(isFind)
54 break;
55 }
56
57 if(!isFind)
58 cout << "no solution" << endl;
59
60 delete gamblers;
61 }
62
63 return 0;
64}
65
66posted on 2009-03-31 20:43
肖羽思 閱讀(909)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ