HDU 4325 FlowersFlowers

92 阅读 0 评论 61 点赞

我是靠谱客的博主花痴人生，最近开发中收集的这篇文章主要介绍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

Sample Output

Case #1:
0
Case #2:
1
2
1

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

思路： 树状数组+离线化

什么是树状数组：http://blog.csdn.net/deng_hui_long/article/details/11066851

总结： 注意 不能使用 Scanner sc = new Scanner(new BufferedInputStream(System.in)); 否则会超时：

 使用 InputStreamReader in=new InputStreamReader(System.in);
      BufferedReader bu=new BufferedReader(in);   可以避免超时

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;
		}
		
	}
}