博罗企业网站建设,硬件工程师都没人干了,宁波网站建设公司名单推荐,科技广告公司网站建设题目描述#xff1a;给出n棵树的高度#xff0c;每棵树上都站着一只鸟#xff0c;枪手Jack站在最左边那棵树的左边对鸟进行射击#xff0c;当Jack在高度为H的地方向右发射一颗子弹的时候#xff0c;高度为H的树上的鸟儿就会掉落#xff08;注#xff1a;其他树上的鸟儿不…题目描述给出n棵树的高度每棵树上都站着一只鸟枪手Jack站在最左边那棵树的左边对鸟进行射击当Jack在高度为H的地方向右发射一颗子弹的时候高度为H的树上的鸟儿就会掉落注其他树上的鸟儿不会飞走或掉落这不是脑经急转弯。Jack会射击多次他想知道每次射击会有多少鸟儿掉落下来。 思路题意十分清晰思路也很简单只要实现这种映射关系就行了数据量比较大。 方法1mapIO外挂水之 1 #include cstdio2 #include cctype3 #include map4 using namespace std;5 6 mapint, int mp;7 int n, m, tmp;8 char buffer[10];9
10 void print_d( int x )
11 {
12 if ( x 0 )
13 {
14 putchar(0);
15 }
16 else
17 {
18 int p 0;
19 while ( x )
20 {
21 buffer[p] x % 10 0;
22 x x / 10;
23 }
24 for ( int i p - 1; i 0; i-- )
25 {
26 putchar(buffer[i]);
27 }
28 }
29 putchar(\n);
30 }
31
32 void scan_d( int x )
33 {
34 char ch getchar();
35 while ( !isdigit(ch) ) ch getchar();
36 x 0;
37 do
38 {
39 x x * 10 ch - 0;
40 ch getchar();
41 } while ( isdigit(ch) );
42 }
43
44 int main ()
45 {
46 while ( scanf(%d%d, n, m) ! EOF )
47 {
48 mp.clear();
49 while ( n-- )
50 {
51 scan_d(tmp);
52 mp[tmp];
53 }
54 while ( m-- )
55 {
56 scan_d(tmp);
57 print_d(mp[tmp]);
58 mp[tmp] 0;
59 }
60 }
61 return 0;
62 } 这样写完全是对的不过比csc的代码要慢一点原因如下 当调用mp[tmp]的时候如果tmp在map中不存在则默认会插入一个tmp到0的映射然后返回所以这样写会让节点数增多查询效率变低。 证明代码如下 1 #include iostream2 #include cstdlib3 #include map4 using namespace std;5 6 int main ()7 {8 mapint, int mp;9 cout mp is empty: mp.size() endl;
10 cout mp[111] endl;
11 cout The size is: mp.size() endl;
12 cout mp[222] endl;
13 cout The size is: mp.size() endl;
14 for ( mapint, int::iterator it mp.begin(); it ! mp.end(); it )
15 {
16 cout it-first maps into it-second endl;
17 }
18 system(pause);
19 return 0;
20 } 运行结果如下 可见确实是这样因此可以这样写来加快效率 1 #include cstdio2 #include map3 using namespace std;4 5 mapint, int mp;6 int n, m, tmp;7 8 int main ()9 {
10 while ( scanf(%d%d, n, m) ! EOF )
11 {
12 mp.clear();
13 while ( n-- )
14 {
15 scanf(%d, tmp);
16 mp[tmp];
17 }
18 while ( m-- )
19 {
20 scanf(%d, tmp);
21 if ( mp.count(tmp) )
22 {
23 printf(%d\n, mp[tmp]);
24 mp.erase(tmp);
25 }
26 else
27 {
28 printf(0\n);
29 }
30 }
31 }
32 return 0;
33 } 不过实测差不多关键可能还是hdu服务器不稳定吧不过mp[tmp] 0; 还是没有 mp.erase(tmp); 好前者删除节点后者只是修改映射的值前者配合mp.count(tmp)理论上更胜一筹。 方法2二分 略... 方法3hash 1 #include cstdio2 #include cstring3 using namespace std;4 5 const int N 5000007;6 int hash_table[N];7 int cnt[N];8 int n, m, tmp;9
10 int hash_key( int key )
11 {
12 return key % N;
13 }
14
15 int kth( int k )
16 {
17 int r ( k 1 ) 1;
18 if ( k 1 ) return r * r;
19 return -r * r;
20 }
21
22 void insert( int key )
23 {
24 int t hash_key(key);
25 for ( int i 0; ; i )
26 {
27 int pos t kth(i);
28 if ( pos 0 ) pos N;
29 if ( pos N ) pos - N;
30 if ( hash_table[pos] -1 )
31 {
32 hash_table[pos] key;
33 cnt[pos];
34 return ;
35 }
36 else if ( hash_table[pos] key )
37 {
38 cnt[pos];
39 return ;
40 }
41 }
42 }
43
44 int find( int key )
45 {
46 int t hash_key(key);
47 for ( int i 0; ; i )
48 {
49 int pos t kth(i);
50 if ( pos 0 ) pos N;
51 if ( pos N ) pos - N;
52 if ( hash_table[pos] key )
53 {
54 int r cnt[pos];
55 cnt[pos] 0;
56 return r;
57 }
58 else if ( hash_table[pos] -1 )
59 {
60 return 0;
61 }
62 }
63 }
64
65 int main ()
66 {
67 while ( scanf(%d%d, n, m) ! EOF )
68 {
69 memset( hash_table, -1, sizeof(hash_table) );
70 memset( cnt, 0, sizeof(cnt) );
71 while ( n-- )
72 {
73 scanf(%d, tmp);
74 insert(tmp);
75 }
76 while ( m-- )
77 {
78 scanf(%d, tmp);
79 printf(%d\n, find(tmp));
80 }
81 }
82 return 0;
83 } 转载于:https://www.cnblogs.com/huoxiayu/p/4393062.html
