求给定值的连续序列
例如给定值是 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.cppblog.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 阅读(84)
评论(0) 编辑 收藏 引用