我是靠谱客的博主 花痴人生,这篇文章主要介绍HDU 4325 FlowersFlowers,现在分享给大家,希望可以做个参考。

Flowers

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1927 Accepted Submission(s): 949


Problem Description
As is known to all, the blooming time and duration varies between different kinds of flowers. Now there is a garden planted full of flowers. The gardener wants to know how many flowers will bloom in the garden in a specific time. But there are too many flowers in the garden, so he wants you to help him.

Input
The first line contains a single integer t (1 <= t <= 10), the number of test cases.
For each case, the first line contains two integer N and M, where N (1 <= N <= 10^5) is the number of flowers, and M (1 <= M <= 10^5) is the query times.
In the next N lines, each line contains two integer S i and T i (1 <= S i <= T i <= 10^9), means i-th flower will be blooming at time [S i, T i].
In the next M lines, each line contains an integer T i, means the time of i-th query.

Output
For each case, output the case number as shown and then print M lines. Each line contains an integer, meaning the number of blooming flowers.
Sample outputs are available for more details.

Sample Input
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 1 1 5 10 4 2 3 1 4 4 8 1 4 6

Sample Output
复制代码
1
2
3
4
5
6
Case #1: 0 Case #2: 1 2 1
复制代码
1
 
复制代码
1

题意:给出n个区间,【s,t】,区间,代表这个时间段有一朵花。m个询问,每次询问一个时间点,输出该时间的花的数量。

复制代码
1
思路: 树状数组+离线化
复制代码
1
什么是树状数组:http://blog.csdn.net/deng_hui_long/article/details/11066851
复制代码
1
总结: 注意 不能使用 Scanner sc = new Scanner(new BufferedInputStream(System.in)); 否则会超时:
复制代码
1
复制代码
1
2
使用 InputStreamReader in=new InputStreamReader(System.in);    BufferedReader bu=new BufferedReader(in); 可以避免超时
复制代码
1
复制代码
1
 
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
复制代码
import java.io.*;
import java.util.*;
/*
 *
 * author : deng_hui_long 
 * Date   : 2013-9-5
 *
*/
public class Main {
	int t,n,m,id;
	int MAX=200000;
	int[] a=new int[MAX];
	int[] c=new int[MAX];
	public static void main(String[] args) throws NumberFormatException, IOException{
		new Main().work();
	}
	void work()throws IOException{
		
		InputStreamReader in=new InputStreamReader(System.in);
		BufferedReader bu=new BufferedReader(in);
		
		t=Integer.parseInt(bu.readLine());
		
		for(int p=1;p<=t;p++){
			System.out.println("Case #"+p+":");
			String ss[]=bu.readLine().split(" ");
			n=Integer.parseInt(ss[0]);
			m=Integer.parseInt(ss[1]);
			
			int nn=n<<1;
			int mm=nn+m;
			
			Node[] node=new Node[mm];
			int i=0;
			for(;i<nn;i++){
				ss=bu.readLine().split(" ");
				
				node[i]=new Node();
				node[i].val=Integer.parseInt(ss[0]);
				node[i].num=i;// 给每个数标号
				
				i++;
				node[i]=new Node();
				node[i].val=Integer.parseInt(ss[1]);
				node[i].num=i;
				
			}
			
			for(;i<mm;i++){
				node[i]=new Node();
				node[i].val=Integer.parseInt(bu.readLine());
				node[i].num=i;
			}
			
			// 排序
			Arrays.sort(node);
			//离散化
			id=1;
			a[node[0].num]=id;
			for(i=1;i<mm;i++){
				if(node[i].val!=node[i-1].val)
					a[node[i].num]=++id;
				else
					a[node[i].num]=id;
			}
			
			//更新
			Arrays.fill(c,0);
			for(i=0;i<nn;i++){
				plus(a[i++],1);
				plus(a[i]+1,-1);
			}
			
			//求和
			for(i=nn;i<mm;i++){
				System.out.println(getSum(a[i]));
			}
			
		}
	}
	
	void plus(int pos, int x) {
		while (pos <= id) {
			c[pos] += x;
			pos += lowbit(pos);
		}
	}
	
	int getSum(int x) {
		int sum = 0;
		while (x > 0) {
			sum += c[x];
			x -= lowbit(x);
		}
		return sum;
	}
	
	int lowbit(int x) {
		return x & (-x);
	}
	
	class Node implements Comparable<Node>{
		int val;
		int num;
		public int compareTo(Node o) {
			return this.val>o.val?1:-1;
		}
		
	}
}

最后

以上就是花痴人生最近收集整理的关于HDU 4325 FlowersFlowers的全部内容,更多相关HDU内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(121)

评论列表共有 0 条评论

立即
投稿
返回
顶部