学步园

posters

描述

The citizens of Bytetown, AB, could not stand that the
candidates in the mayoral election campaign have been placing their
electoral posters at all places at their whim. The city council has
finally decided to build an electoral wall for placing the posters
and introduce the following rules:
• Every candidate can place exactly one poster on the wall.
• All posters are of the same height equal to the height of the
wall; the width of a poster can be any integer number of bytes
(byte is the unit of length in Bytetown).
• The wall is divided into segments and the width of each segment
is one byte.
• Each poster must completely cover a contiguous number of wall
segments.

They have built a wall 10000000 bytes long (such that there is
enough place for all candidates). When the electoral campaign was
restarted, the candidates were placing their posters on the wall
and their posters differed widely in width. Moreover, the
candidates started placing their posters on wall segments already
occupied by other posters. Everyone in Bytetown was curious whose
posters will be visible (entirely or in part) on the last day
before elections.
Your task is to find the number of visible posters when all the
posters are placed given the information about posters' size, their
place and order of placement on the electoral wall.

输入

The first line of input contains a number c giving the number
of cases that follow. The first line of data for a single case
contains number 1 <= n <= 10000. The subsequent n lines
describe the posters in the order in which they were placed. The
i-th line among the n lines contains two integer numbers li and ri
which are the number of the wall segment occupied by the left end
and the right end of the i-th poster, respectively. We know that
for each 1 <= i <= n, 1 <= li <= ri <= 10000000.
After the i-th poster is placed, it entirely covers all wall
segments numbered li, li+1 ,... , ri.

输出

For each input data set print the number of visible posters
after all the posters are placed.

The picture below illustrates the case of the sample input.

http://acm.pku.edu.cn/JudgeOnline/images/2528_1.jpg

样例输入

1
5
1 4
2 6
8 10
3 4
7 10

样例输出

4

来源

POJ

上传者

iphxer

      这道题用到了线段树和离散化2个概念，1方面帖海报的过程就是对线段的节点进行染色的过程，另外一方面申请1000K的墙这个对内存的消耗太大了，并且在检索的时候效率也很低，这时候考虑到海报只有1W，那么我们可以针对海报做处理，思考最后的结果，每一块海报张贴的区域应该是可以由开始节点和结束节点确定的，那么我们需要考虑的点做多只有2W，但是这时候要考虑如果我们对海报的开始和结束位置进行离散化那么就有一些信息丢失掉了，比如如下两组数据

1-10 1-4 5-10

1-10 1-4 6-10

第一个案例运气好还能通过，第二个案例在对顶点离散完之后剩  1 4 6
10   
5-5这段区域被丢失掉了，这块区域总是出现在某一个海报末尾之后连续区域，我们可以用那张海报的末尾节点+1来表示这块区域，那么我们可以将所有末尾节点加一加入原始数据再对数据进行离散，这样原始数据就不会丢失了，一下是实现代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

//线段树的实现
public class PosterV1 {
    int
size;
    int
nodes;
    final int
maxn = 11111;
    boolean[]
statistic = new boolean[maxn];
    int[]
leftVertux = new int[maxn];
    int[]
rightVertux = new int[maxn];
    int[] tree =
new int[maxn << 4];
    ArrayList
temp = new ArrayList(maxn*3);

    public
static void main(String[] args) {
   
    PosterV1
poster = new PosterV1();
   
   
poster.solution();
    }

    //
程序入口
    public void
solution() {
   
    Scanner in =
new Scanner(System.in);
   
    int cases =
in.nextInt();
   
    while
(cases-- > 0) {
   
   
   
init();

   
   
    //
获取海报的左右坐标
   
   
    nodes =
in.nextInt();
   
   
    for (int i =
1; i <= nodes; i++) {
   
   
   
   
leftVertux[i] = in.nextInt();
   
   
   
   
rightVertux[i] = in.nextInt();
   
   
   
   
temp.add(leftVertux[i]);
   
   
   
   
temp.add(rightVertux[i]);
   
   
    }
   
   
    //
将海报的坐标离散化， 这里用到的处理丢失数据的方案比我上面分析的要差
   
   
   
Collections.sort(temp);
   
   
    for (int i =
1; i < temp.size(); i++) {
   
   
   
    if
(temp.get(i) == temp.get(i - 1)) {
   
   
   
   
   
temp.remove(i);
   
   
   
   
    i--;
   
   
   
    }