110MS, O(nlog(n))的算法,怎样才能更快?那些10几个MS的是怎样实现的?
1 Source Code
2 Problem: 1631 User: goldenlock
3 Memory: 628K Time: 110MS
4 Language: G++ Result: Accepted
5
6 * Source Code
7
8 /**
9 * ==============================================================================
10 *
11 * \file bridging_signals_1631.cc
12 *
13 * \author pku_goldenlock@qq.com
14 *
15 * \date 2009-10-28 21:41:57.539397
16 *
17 * Description: pku 1631,
18 * 本质上就是求最长只增序列,编程之美上
19 * 有解释.下面只要提到序列就是递增序列.
20 * 疑问,两个左边的指向同一个右边的算相交了吗?假定不算相交
21 * 不算的话就允许递增序列有相同大小的元素,如果算就不能有.
22 * 不管算不算相交,都是求upper_bound,如果不算的化,元素全
23 * 不相同.恩,本题目是没有相同元素的,不会左边两个连右边
24 * 同一个的.但是解法并不改变.
25 * 思路:
26 * 依次求以第n个元素结尾的只增序列长度l[n],记录所有的l[]最大的一个即
27 * 为所求.
28 * 核心优化:
29 * 最本质的规律是前面的l[k],l[j]相等的化, 假如data[k] < data[j]
30 * 那么后面元素就不需要去考虑data[j]!在同等长度下,尾元素小的序
31 * 列优先.
32 *
33 * 因此可以记录各个长度的序列,记录其对应的最小尾元素.
34 * 考虑长度为i(1,2,3,4
.)这样的递增长度序列,其对应的最小尾元素t[i]也
35 * 是递增的.否则假如如果i > j 而t[i] < t[j] 则存在 x < t[i] < t[j]
36 * l[x] = t[j] 与t[j] 是长度为j的序列的最小尾元素矛盾.
37 *
38 * 因为递增长度对应的最小尾元素也递增,所以可以二分查找.
39 * 对于扫描到第n个元素, data[n],去最小尾元素序列二分查找
40 * data[n](stl upper_bound),返回第一个比data[n]大的位置k,令t[k] = data[n],
41 * 即更新长度位k的序列的最小尾元素值.
42 * 最后返回最长的那个序列的长度即可.
43 *
44 * ==============================================================================
45 */
46 #include <stdio.h>
47 /*
48 * for spped, your response to let end >= 0
49 * 对这个特殊的问题,没有相同元素,所以一定查找不到key
50 * 如1 2 4 查找3 返回index 2 t[2] = 4(upper_bound!)
51 * upper_bound和lower_bound的区别在于 upper_bound return start, lower_bound return end.
52 * search 1.5
53 * 1
54 * end start
55 * search 0.5
56 * 1
57 * end start
58 * 最后总是start指向比key大的第一个数字位置,end指向比key小的第一个位置
59 * the last status : end key start
60 * TODO try std::upper_bound, the same:)
61 */
62 inline int upper_bound(int t[], int end, int key) {
63 int start = 0;
64 int mid;
65 while (start <= end) {
66 mid = (start + end)/2;
67 //考虑假设有相同元素的情况(本题目没有),必须这么写,不能key <= t[mid],i
68 //lower_bound 要写 if key > t[mid] start = mid + 1
69 if (key < t[mid])
70 end = mid - 1;
71 else
72 start = mid + 1;
73 }
74 return start;
75 }
76
77 inline int maxIncreasingSequence(int data[], int len)
78 {
79 //--------------------init
80 int max_len = 0;
81 int t[len];
82 t[0] = data[0];
83 int pos;
84 //--------------------find max length
85 for (int i = 1; i < len; i++) {
86 pos = upper_bound(t, max_len, data[i]);
87 if (pos > max_len) //get longer sequence
88 max_len = pos;
89 //modify(or add) the smallest ending value
90 //for sequence with length as pos + 1
91 t[pos] = data[i];
92 }
93 //--------------------return
94 return max_len + 1; //due to staring index is 1 not 0
95 }
96
97 int main(int argc, char *argv[])
98 {
99 int test_num;
100 scanf("%d", &test_num);
101 int array_length;
102 //-----------------run each test case
103 for (int i = 0; i < test_num; i++) {
104 //------------------------get input
105 scanf("%d", &array_length);
106 int data[array_length];
107 for (int j = 0; j < array_length; j++) {
108 scanf("%d", &data[j]);
109 }
110 //------------------------print result
111 printf("%d\n", maxIncreasingSequence(data, array_length));
112 }
113 return 0;
114 }
115
116
2 Problem: 1631 User: goldenlock
3 Memory: 628K Time: 110MS
4 Language: G++ Result: Accepted
5
6 * Source Code
7
8 /**
9 * ==============================================================================
10 *
11 * \file bridging_signals_1631.cc
12 *
13 * \author pku_goldenlock@qq.com
14 *
15 * \date 2009-10-28 21:41:57.539397
16 *
17 * Description: pku 1631,
18 * 本质上就是求最长只增序列,编程之美上
19 * 有解释.下面只要提到序列就是递增序列.
20 * 疑问,两个左边的指向同一个右边的算相交了吗?假定不算相交
21 * 不算的话就允许递增序列有相同大小的元素,如果算就不能有.
22 * 不管算不算相交,都是求upper_bound,如果不算的化,元素全
23 * 不相同.恩,本题目是没有相同元素的,不会左边两个连右边
24 * 同一个的.但是解法并不改变.
25 * 思路:
26 * 依次求以第n个元素结尾的只增序列长度l[n],记录所有的l[]最大的一个即
27 * 为所求.
28 * 核心优化:
29 * 最本质的规律是前面的l[k],l[j]相等的化, 假如data[k] < data[j]
30 * 那么后面元素就不需要去考虑data[j]!在同等长度下,尾元素小的序
31 * 列优先.
32 *
33 * 因此可以记录各个长度的序列,记录其对应的最小尾元素.
34 * 考虑长度为i(1,2,3,4
.)这样的递增长度序列,其对应的最小尾元素t[i]也35 * 是递增的.否则假如如果i > j 而t[i] < t[j] 则存在 x < t[i] < t[j]
36 * l[x] = t[j] 与t[j] 是长度为j的序列的最小尾元素矛盾.
37 *
38 * 因为递增长度对应的最小尾元素也递增,所以可以二分查找.
39 * 对于扫描到第n个元素, data[n],去最小尾元素序列二分查找
40 * data[n](stl upper_bound),返回第一个比data[n]大的位置k,令t[k] = data[n],
41 * 即更新长度位k的序列的最小尾元素值.
42 * 最后返回最长的那个序列的长度即可.
43 *
44 * ==============================================================================
45 */
46 #include <stdio.h>
47 /*
48 * for spped, your response to let end >= 0
49 * 对这个特殊的问题,没有相同元素,所以一定查找不到key
50 * 如1 2 4 查找3 返回index 2 t[2] = 4(upper_bound!)
51 * upper_bound和lower_bound的区别在于 upper_bound return start, lower_bound return end.
52 * search 1.5
53 * 1
54 * end start
55 * search 0.5
56 * 1
57 * end start
58 * 最后总是start指向比key大的第一个数字位置,end指向比key小的第一个位置
59 * the last status : end key start
60 * TODO try std::upper_bound, the same:)
61 */
62 inline int upper_bound(int t[], int end, int key) {
63 int start = 0;
64 int mid;
65 while (start <= end) {
66 mid = (start + end)/2;
67 //考虑假设有相同元素的情况(本题目没有),必须这么写,不能key <= t[mid],i
68 //lower_bound 要写 if key > t[mid] start = mid + 1
69 if (key < t[mid])
70 end = mid - 1;
71 else
72 start = mid + 1;
73 }
74 return start;
75 }
76
77 inline int maxIncreasingSequence(int data[], int len)
78 {
79 //--------------------init
80 int max_len = 0;
81 int t[len];
82 t[0] = data[0];
83 int pos;
84 //--------------------find max length
85 for (int i = 1; i < len; i++) {
86 pos = upper_bound(t, max_len, data[i]);
87 if (pos > max_len) //get longer sequence
88 max_len = pos;
89 //modify(or add) the smallest ending value
90 //for sequence with length as pos + 1
91 t[pos] = data[i];
92 }
93 //--------------------return
94 return max_len + 1; //due to staring index is 1 not 0
95 }
96
97 int main(int argc, char *argv[])
98 {
99 int test_num;
100 scanf("%d", &test_num);
101 int array_length;
102 //-----------------run each test case
103 for (int i = 0; i < test_num; i++) {
104 //------------------------get input
105 scanf("%d", &array_length);
106 int data[array_length];
107 for (int j = 0; j < array_length; j++) {
108 scanf("%d", &data[j]);
109 }
110 //------------------------print result
111 printf("%d\n", maxIncreasingSequence(data, array_length));
112 }
113 return 0;
114 }
115
116
可以复用data数组,即不需要t数组,不过不改善什么性能.
1 #include <stdio.h>
2
3 inline int upper_bound(int data[], int end, int key) {
4 int start = 0;
5 int mid;
6 while (start <= end) {
7 mid = (start + end)/2;
8 //考虑假设有相同元素的情况(本题目没有),必须这么写,不能key <= t[mid],i
9 //lower_bound 要写 if key > t[mid] start = mid + 1
10 if (key < data[mid])
11 end = mid - 1;
12 else
13 start = mid + 1;
14 }
15 return start;
16 }
17
18 inline int maxIncreasingSequence(int data[], int len)
19 {
20 //--------------------init
21 int max_len = 0;
22 int pos;
23 //--------------------find max length
24 for (int i = 1; i < len; i++) {
25 pos = upper_bound(data, max_len, data[i]);
26 if (pos > max_len) //get longer sequence
27 max_len = pos;
28 data[pos] = data[i]; //modify smallest tail value
29 }
30 //--------------------return
31 return max_len + 1; //due to staring index is 1 not 0
32 }
33
34 int main(int argc, char *argv[])
35 {
36 int test_num;
37 scanf("%d", &test_num);
38 int array_length;
39 //-----------------run each test case
40 for (int i = 0; i < test_num; i++) {
41 //------------------------get input
42 scanf("%d", &array_length);
43 int data[array_length];
44 for (int j = 0; j < array_length; j++) {
45 scanf("%d", &data[j]);
46 }
47 //------------------------print result
48 printf("%d\n", maxIncreasingSequence(data, array_length));
49 }
50 return 0;
51 }
52
53
2
3 inline int upper_bound(int data[], int end, int key) {
4 int start = 0;
5 int mid;
6 while (start <= end) {
7 mid = (start + end)/2;
8 //考虑假设有相同元素的情况(本题目没有),必须这么写,不能key <= t[mid],i
9 //lower_bound 要写 if key > t[mid] start = mid + 1
10 if (key < data[mid])
11 end = mid - 1;
12 else
13 start = mid + 1;
14 }
15 return start;
16 }
17
18 inline int maxIncreasingSequence(int data[], int len)
19 {
20 //--------------------init
21 int max_len = 0;
22 int pos;
23 //--------------------find max length
24 for (int i = 1; i < len; i++) {
25 pos = upper_bound(data, max_len, data[i]);
26 if (pos > max_len) //get longer sequence
27 max_len = pos;
28 data[pos] = data[i]; //modify smallest tail value
29 }
30 //--------------------return
31 return max_len + 1; //due to staring index is 1 not 0
32 }
33
34 int main(int argc, char *argv[])
35 {
36 int test_num;
37 scanf("%d", &test_num);
38 int array_length;
39 //-----------------run each test case
40 for (int i = 0; i < test_num; i++) {
41 //------------------------get input
42 scanf("%d", &array_length);
43 int data[array_length];
44 for (int j = 0; j < array_length; j++) {
45 scanf("%d", &data[j]);
46 }
47 //------------------------print result
48 printf("%d\n", maxIncreasingSequence(data, array_length));
49 }
50 return 0;
51 }
52
53