求給定值的連續序列
例如給定值是 15
則有：
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
求解
設定一個區間 [left, right]
計算 left 到 right 之間的所有和 sum
若 sum 小于給定值 n 則 right 右移
若 sum 大于給定值 n 則 left 右移
若 sum 等于給定值 n 則 left 右移
[left, right] 的初始是 [1, 1]
另一個問題
求解一個集合中兩個元素之和等于給定值
先對這個集合進行排序，然后從兩端遍歷，若和大于給定值則右邊的標記左移，若和小于給定值則左邊的值右移。
http://www.shnenglu.com/jake1036/archive/2011/05/19/146745.html
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 int bar(int left, int right)
6 {
7 return (left + right) * (right - left + 1) / 2;
8 }
9
10 void foo(vector<vector<int> >& result, int n)
11 {
12 result.clear();
13 int left = 1, right = 1;
14 int t;
15 while (left <= n / 2)
16 {
17 t = bar(left, right);
18 if (t < n)
19 {
20 ++right;
21 }
22 else if (t > n)
23 {
24 ++left;
25 }
26 else
27 {
28 vector<int> v;
29 for (int i = left; i <= right; ++i)
30 {
31 v.push_back(i);
32 }
33 result.push_back(v);
34 ++left;
35 }
36 }
37 }
38
39 int main()
40 {
41 int n;
42 vector<vector<int> > result;
43 while (cin >> n)
44 {
45 foo(result, n);
46 for (vector<vector<int> >::size_type i = 0; i != result.size(); ++i)
47 {
48 for (vector<int>::size_type j = 0; j != result[i].size(); ++j)
49 {
50 cout << result[i][j] << ' ';
51 }
52 cout << endl;
53 }
54 }
55 return 0;
56 }
posted on 2011-07-23 16:23
unixfy 閱讀(106)
評論(0) 編輯 收藏 引用