首页 > ACM题库 > 九度OJ > 九度-1088-剩下的树[解题代码]
2013
12-12

九度-1088-剩下的树[解题代码]

题目来源:2011年清华大学计算机研究生机试真题

题目描述:

    有一个长度为整数L(1<=L<=10000)的马路,可以想象成数轴上长度为L的一个线段,起点是坐标原点,在每个整数坐标点有一棵树,即在0,1,2,…,L共L+1个位置上有L+1棵树。
    现在要移走一些树,移走的树的区间用一对数字表示,如 100 200表示移走从100到200之间(包括端点)所有的树。
    可能有M(1<=M<=100)个区间,区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。

输入:

    两个整数L(1<=L<=10000)和M(1<=M<=100)。
    接下来有M组整数,每组有一对数字。

输出:

    可能有多组输入数据,对于每组输入数据,输出一个数,表示移走所有区间的树之后剩下的树的个数。

样例输入:
500 3
100 200
150 300
470 471
样例输出:
298

java 代码如下:
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int l;
	static int m;
	static int arr[];
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNextInt()){
			l = s.nextInt();
			m = s.nextInt();
			arr = new int[l+1];
			for(int i=0; i<m; i++)
				Arrays.fill(arr, s.nextInt(), s.nextInt()+1, 1);
			int count = 0;
			for(int i:arr)
				if(i == 0)
					count ++;
			System.out.println(count);
		}
	}

}

/**************************************************************
	Problem: 1088
	User: coder
	Language: Java
	Result: Accepted
	Time:2740 ms
	Memory:29728 kb
****************************************************************/


  1. […] SAO Utils:国人开发,有史以来最酷炫的程序启动菜单,实在酷炫,真心酷炫,特别酷炫。SAO Utils – SAO风格启动菜单开发日志 […]

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  3. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥