讨论下这几种算法[寻高效的算法]

Susake_

回复 10# ID好难
说到线段树还真想试试(应该算是第一次有这种冲动)~一直都觉得线段树的代码太多！


   

Kurosaki_Ichigo

ID好难 发表于 2014-09-09 15:00
回复 7# Susake_

很显然二分写的不够好。 用线段树也可以解决这个问题吧，如果是动态插入查询，二分就不 ...

回复的是7楼，那你指的应该是第一题吧。何以见得这二分显然不够好呢？烦请好好说明一下。同时很想看看你用线段树怎么解决，最好附上代码。

qiwei9743

回复 2# Susake_

你好楼主，求指点，没想明白为什么可以用二分，因为您题目里面没有说是有序的啊？
   
谢谢。

ID好难

Kurosaki_Ichigo 发表于 2014-09-10 09:53
回复的是7楼，那你指的应该是第一题吧。何以见得这二分显然不够好呢？烦请好好说明一下。同时很想看看你 ...

回复 12# Kurosaki_Ichigo

二分可以用STL 里面的lower_bound/upper_bound。
线段树应该比较容易理解吧，在区间 [a,b] 中添加一个count 来记录区间[a,b]中一共有多少个数字， 查询序列中比ai大的有几个，相当于查询区间[ai, 最大上限] 有多少个数。

Kurosaki_Ichigo

ID好难 发表于 2014-09-10 12:52
回复 12# Kurosaki_Ichigo

二分可以用STL 里面的lower_bound/upper_bound。
线段树应该比较容易理解吧，在区间 [a,b] 中添加一个count 来记录区间[a,b]中一共有多少个数字， 查询序列中比ai大的有几个，相当于查询区间[ai, 最大上限] 有多少个数。

呵呵一维数组的查找还用的着线段树？要是你听说过区间树会不会觉得它更适合呢？

这样吧，咱别光停留在嘴上，针对第一题你写段线段树的代码，只要能得出正确的结果，不论效率如何，我把我所有的积分都送你。也不限语言，用你最称手的。

Susake_

qiwei9743 发表于 2014-09-10 11:29
回复 2# Susake_

你好楼主，求指点，没想明白为什么可以用二分，因为您题目里面没有说是有序的啊？

是无序的！
可能你是单单就一次查询看的，而我考虑的是动态查询~
顺便试了试你说的upper_bound

1. 
   
2. #include <bits/stdc++.h>
   
3. 
   
4. std::vector <int> A(5);
   
5. 
   
6. int main(int argc, char *argv[])
   
7. {
   
8.     A[0] = 1;A[1] = 2;A[2] = 3;A[3] = 3;A[4] = 5;
   
9.     for(int i = 0; i < A.size(); i++)
   
10.         std::cout << A.size() - (upper_bound(A.begin(), A.end(), A[i]) - A.begin()) << "\n";
    
11.         return 0;
    
12. }
    

复制代码

Susake_

感觉第一题还能将难度提升，那就是将操作改为   (动态插入，删除，查询)~^_^

ID好难

回复 15# Kurosaki_Ichigo


    我说的是可以用线段树，并且它可以处理动态插入查询的情况。这个问题应该也可以用树状数组来写
    呵呵，成约架了。。。不至于，你太认真了。。。

cobras

算法5没有发现在哪里。算法4有问题。

1. /* number.c */
   
2. 
   
3. #include <ctype.h>
   
4. #include <stdio.h>
   
5. #include <stdlib.h>
   
6. #include <string.h>
   
7. 
   
8. #define ALEN(a) (sizeof(a)/sizeof((a)[0]))
   
9. 
   
10. int get_line(char *buf, int buf_len, int *o_len)
    
11. {
    
12.         if (fgets(buf, buf_len, stdin) != NULL) {
    
13.                 if (o_len != NULL) {
    
14.                         *o_len = strlen(buf);
    
15.                 }
    
16.                 return 0;
    
17.         }
    
18.         return -1;
    
19. }
    
20. 
    
21. int get_number(const char *s, int off, int lmt, int *o_off, int *o_val)
    
22. {
    
23.         const char *pstart;
    
24.         char *pend;
    
25.         int len;
    
26.         long value;
    
27. 
    
28.         if (off < lmt) {
    
29.                 pstart = s + off;
    
30.                 pend = (char *)pstart;
    
31.                 value = strtol(pstart, &pend, 10);
    
32.                 if (pend != pstart) {
    
33.                         len = pend - s;
    
34.                         if (len <= lmt) {
    
35.                                 *o_off = len;
    
36.                                 *o_val = value;
    
37.                                 return 0;
    
38.                         }
    
39.                 }
    
40.         }
    
41.         return -1;
    
42. }
    
43. 
    
44. int get_numbers(const char *text, int *o_array, int a_len, int *o_len)
    
45. {
    
46.         char line_buf[256];
    
47.         int lmt;
    
48.         int off;
    
49.         int i;
    
50. 
    
51.         printf("%s: ", text == NULL ? "" : text);
    
52.         if (get_line(line_buf, sizeof(line_buf), &lmt) == 0) {
    
53.                 off = 0;
    
54.                 for (i = 0; i < a_len; ++i) {
    
55.                         if (get_number(line_buf, off, lmt, &off, &o_array[i]) == 0) {
    
56.                                 continue;
    
57.                         }
    
58.                         break;
    
59.                 }
    
60.                 if (i > 0) {
    
61.                         if (o_len != NULL) {
    
62.                                 *o_len = i;
    
63.                         }
    
64.                         return 0;
    
65.                 }
    
66.         }
    
67.         return -1;
    
68. }
    
69. 
    
70. int select_menu(void)
    
71. {
    
72.         const char *menu_text[] = {
    
73.                 "1 input numbers and query greater numbers",
    
74.                 "2 input double column numbers and query greater numbers",
    
75.                 "3 input triple column numbers and query greater numbers",
    
76.                 "4 input numbers and do operations",
    
77.                 "5",
    
78.                 "6 quit",
    
79.         };
    
80.         int i;
    
81.         int val;
    
82. 
    
83.         for (;;) {
    
84.                 for (i = 0; i < ALEN(menu_text); ++i) {
    
85.                         puts(menu_text[i]);
    
86.                 }
    
87.                 if (get_numbers("Please input the menu number", &val, 1, NULL) == 0) {
    
88.                         if (val >= 1 && val <= ALEN(menu_text)) {
    
89.                                 return val;
    
90.                         }
    
91.                 }
    
92.                 puts("ERROR: invalid input, input again");
    
93.         }
    
94. }
    
95. 
    
96. int compare_numbers(const int *num1, const int *num2, int cnt)
    
97. {
    
98.         int i;
    
99. 
    
100.         for (i = 0; i < cnt; ++i) {
     
101.                 if (num1[i] <= num2[i]) {
     
102.                         return 0;
     
103.                 }
     
104.         }
     
105.         return 1;
     
106. }
     
107. 
     
108. int query_123(const int *ai, int n, const int *num, int cnt)
     
109. {
     
110.         int i;
     
111.         int counter;
     
112.        
     
113.         counter = 0;
     
114.         for (i = 0; i < n; ++i) {
     
115.                 if (compare_numbers(ai + i * cnt, num, cnt)) {
     
116.                         ++counter;
     
117.                 }
     
118.         }
     
119.         return counter;
     
120. }
     
121. 
     
122. int do_menu_123(int cnt)
     
123. {
     
124.         int n;
     
125.         int m;
     
126.         int num[3];
     
127.         int i;
     
128.         int len;
     
129.         int *ai;
     
130.         int *result;
     
131. 
     
132.         if (get_numbers(NULL, &n, 1, NULL) == 0 && n > 0) {
     
133.                 ai = (int *)malloc(n * sizeof(int) * cnt);
     
134.                 if (ai != NULL) {
     
135.                         memset(ai, 0, n * sizeof(int) * cnt);
     
136.                         if (cnt == 1) {
     
137.                                 for (;;) {
     
138.                                         if (get_numbers(NULL, ai, n, &len) == 0 && len == n) {
     
139.                                                 break;
     
140.                                         }
     
141.                                 }
     
142.                         }else {
     
143.                                 for (i = 0; i < n;) {
     
144.                                         if (get_numbers(NULL, ai + i * cnt, cnt, &len) == 0 && len == cnt) {
     
145.                                                 ++i;
     
146.                                         }
     
147.                                 }
     
148.                         }
     
149.                         if (get_numbers(NULL, &m, 1, NULL) == 0 && m > 0) {
     
150.                                 result = (int *)malloc(m * sizeof(int));
     
151.                                 if (result != NULL) {
     
152.                                         memset(result, 0, sizeof(int) * m);
     
153.                                         for (i = 0; i < m;) {
     
154.                                                 if (get_numbers(NULL, num, cnt, NULL) == 0) {
     
155.                                                         result[i++] = query_123(ai, n, num, cnt);
     
156.                                                 }
     
157.                                         }
     
158.                                         for (i = 0; i < m; ++i) {
     
159.                                                 printf("%d\n", result[i]);
     
160.                                         }
     
161.                                         free(result);
     
162.                                 }
     
163.                         }
     
164.                         free(ai);
     
165.                 }
     
166.         }
     
167.         return 0;
     
168. }
     
169. 
     
170. int get_identifier(const char *s, int off, int lmt, int *o_off)
     
171. {
     
172.         if (isalpha(s[off])) {
     
173.                 do {
     
174.                         ++off;
     
175.                 }while (isalpha(s[off]) || isdigit(s[off]));
     
176.                 *o_off = off;
     
177.                 return 0;
     
178.         }
     
179.         return -1;
     
180. }
     
181. 
     
182. int get_space(const char *s, int off, int lmt, int *o_off)
     
183. {
     
184.         if (isspace(s[off])) {
     
185.                 do {
     
186.                         ++off;
     
187.                 }while (isspace(s[off]));
     
188.                 *o_off = off;
     
189.                 return 0;
     
190.         }
     
191.         return -1;
     
192. }
     
193. 
     
194. int compare_text(const char *s, int off, int lmt, const char *tab[], int tab_len)
     
195. {
     
196.         int len;
     
197.         int i;
     
198. 
     
199.         for (i = 0; i < tab_len; ++i) {
     
200.                 len = strlen(tab[i]);
     
201.                 if (off + len == lmt && strncmp(s + off, tab[i], len) == 0) {
     
202.                         return i;
     
203.                 }
     
204.         }
     
205.         return -1;
     
206. }
     
207. 
     
208. int do_menu_4(void)
     
209. {
     
210.         char line_buf[256];
     
211.         const char *cmd[] = {"a", "d", "q"};
     
212.         const char *var[] = {"a1", "a2"};
     
213.         int a1, a2;
     
214.         int lmt;
     
215.         int off;
     
216.         int next;
     
217.         int cmd_id;
     
218.         int p1;
     
219.         int p2;
     
220.         int val;
     
221.         int n;
     
222.         int i;
     
223. 
     
224.         a1 = 0;
     
225.         a2 = 0;
     
226.         if (get_numbers(NULL, &n, 1, NULL) == 0) {
     
227.                 for (i = 0; i < n; ++i) {
     
228.                         if (get_line(line_buf, sizeof(line_buf), &lmt) == 0) {
     
229.                                 off = 0;
     
230.                                 get_space(line_buf, off, lmt, &off);
     
231.                                 if (get_identifier(line_buf, off, lmt, &next) == 0) {
     
232.                                         cmd_id = compare_text(line_buf, off, next, cmd, ALEN(cmd));
     
233.                                         if (cmd_id != -1) {
     
234.                                                 off = next;
     
235.                                                 switch (cmd_id) {
     
236.                                                 case 0:
     
237.                                                         get_space(line_buf, off, lmt, &off);
     
238.                                                         if (get_identifier(line_buf, off, lmt, &next) == 0) {
     
239.                                                                 cmd_id = compare_text(line_buf, off, next, var, ALEN(var));
     
240.                                                                 if (cmd_id != -1) {
     
241.                                                                         off = next;
     
242.                                                                         if (get_number(line_buf, off, lmt, &off, &val) == 0) {
     
243.                                                                                 switch (cmd_id) {
     
244.                                                                                 case 0:
     
245.                                                                                         a1 += val;
     
246.                                                                                         break;
     
247.                                                                                 case 1:
     
248.                                                                                         a2 += val;
     
249.                                                                                         break;
     
250.                                                                                 }
     
251.                                                                         }
     
252.                                                                 }
     
253.                                                         }
     
254.                                                         break;
     
255.                                                 case 1:
     
256.                                                         get_space(line_buf, off, lmt, &off);
     
257.                                                         if (get_identifier(line_buf, off, lmt, &next) == 0) {
     
258.                                                                 cmd_id = compare_text(line_buf, off, next, var, ALEN(var));
     
259.                                                                 if (cmd_id != -1) {
     
260.                                                                         off = next;
     
261.                                                                         if (get_number(line_buf, off, lmt, &off, &val) == 0) {
     
262.                                                                                 switch (cmd_id) {
     
263.                                                                                 case 0:
     
264.                                                                                         a1 -= val;
     
265.                                                                                         break;
     
266.                                                                                 case 1:
     
267.                                                                                         a2 -= val;
     
268.                                                                                         break;
     
269.                                                                                 }
     
270.                                                                         }
     
271.                                                                 }
     
272.                                                         }
     
273.                                                         break;
     
274.                                                 case 2:
     
275.                                                         get_space(line_buf, off, lmt, &off);
     
276.                                                         if (get_identifier(line_buf, off, lmt, &next) == 0) {
     
277.                                                                 p1 = compare_text(line_buf, off, next, var, ALEN(var));
     
278.                                                                 if (p1 != -1) {
     
279.                                                                         off = next;
     
280.                                                                         get_space(line_buf, off, lmt, &off);
     
281.                                                                         if (get_identifier(line_buf, off, lmt, &next) == 0) {
     
282.                                                                                 p2 = compare_text(line_buf, off, next, var, ALEN(var));
     
283.                                                                                 if (p2 != -1) {
     
284.                                                                                 }
     
285.                                                                         }else {
     
286.                                                                                 switch (p1) {
     
287.                                                                                 case 0:
     
288.                                                                                         printf("%d\n", a1);
     
289.                                                                                         break;
     
290.                                                                                 case 1:
     
291.                                                                                         printf("%d\n", a2);
     
292.                                                                                         break;
     
293.                                                                                 }
     
294.                                                                         }
     
295.                                                                 }
     
296.                                                         }
     
297.                                                         break;
     
298.                                                 }
     
299.                                         }
     
300.                                 }
     
301.                         }
     
302.                 }
     
303.         }
     
304.         return 0;
     
305. }
     
306. 
     
307. int main(void)
     
308. {
     
309.         int menu_do;
     
310. 
     
311.         for (;;) {
     
312.                 menu_do = select_menu();
     
313.                 switch (menu_do) {
     
314.                 case 1:
     
315.                         do_menu_123(1);
     
316.                         break;
     
317.                 case 2:
     
318.                         do_menu_123(2);
     
319.                         break;
     
320.                 case 3:
     
321.                         do_menu_123(3);
     
322.                         break;
     
323.                 case 4:
     
324.                         do_menu_4();
     
325.                 case 5:
     
326.                         break;
     
327.                 case 6:
     
328.                         return 0;
     
329.                 }
     
330.         }
     
331. }
     

复制代码

Susake_

前段时间，听说一个流言，不知道是不是真的？
线段树一般能解决树状数组的问题(这个是树状数组百度百科上说的)
伸展树能解决线段树部分线段树的功能和某些线段树不能完成的功能(至于啥功能不太确定,没真正用过splay)
为此我翻扩展库里面的树结构(没有线段树,但有伸展树,红黑树这些),发现里面有一个,但至今没用上过，也不知道那个作者写来用什么用的？贴出来分享下~
以下是几个简单的操作，其他的也可以套STL里面的那些insert,erase什么

1. #include <bits/stdc++.h>
   
2. #include <ext/pb_ds/assoc_container.hpp>
   
3. #include <ext/pb_ds/priority_queue.hpp>
   
4. #include <ext/pb_ds/tree_policy.hpp>
   
5. #include <ext/pb_ds/trie_policy.hpp>
   
6. 
   
7. std::priority_queue <int> pr_q;__gnu_pbds::trie <std::string, int> trie_t;
   
8. __gnu_pbds::tree <int, int, std::less<int>, __gnu_pbds::splay_tree_tag, __gnu_pbds::tree_order_statistics_node_update> sp_t;
   
9. __gnu_pbds::priority_queue<std::pair <int, int>,std::greater<std::pair <int, int> >, __gnu_pbds::pairing_heap_tag > pa_h;
   
10. 
    
11. int main(int argc, char *argv[])
    
12. {
    
13.     for(int i = 0; i < 3; i++) sp_t[i] = i + 5;
    
14.     for(int i = 0; i < 3; i++)
    
15.         printf("%d %d\n", sp_t.find_by_order(i) -> first, sp_t.find_by_order(i) -> second);
    
16.         return 0;
    
17. }

复制代码