首页 > 基础算法 > 递推 > Problem B. GBus count-Google APAC 2015
2014
11-15

Problem B. GBus count-Google APAC 2015

Problem B. GBus count

There exists a straight line along which cities are built.

Each city is given a number starting from 1. So if there are 10 cities, city 1 has a number 1, city 2 has a number 2,… city 10 has a number 10.

Different buses (named GBus) operate within different cities, covering all the cities along the way. The cities covered by a GBus are represented as ‘first_city_number last_city_number’ So, if a GBus covers cities 1 to 10 inclusive, the cities covered by it are represented as ’1 10′

We are given the cities covered by all the GBuses. We need to find out how many GBuses go through a particular city.

Input

The first line contains the number of test cases (T), after which T cases follow each separated from the next with a blank line.
For each test case,
The first line contains the number of GBuses.(N)
Second line contains the cities covered by them in the form
a1 b1 a2 b2 a3 b3…an bn
where GBus1 covers cities numbered from a1 to b1, GBus2 covers cities numbered from a2 to b2, GBus3 covers cities numbered from a3 to b3, upto N GBuses.
Next line contains the number of cities for which GBus count needs to be determined (P).
The below P lines contain different city numbers.

Output

For each test case, output one line containing “Case #Ti:” followed by P numbers corresponding to the number of cities each of those P GBuses goes through.

样例:

Input 	
2
4
15 25 30 35 45 50 10 20
2
15
25
10
10 15 5 12 40 55 1 10 25 35 45 50 20 28 27 35 15 40 4 5
3
5
10
27
Output 
Case #1: 2 1
Case #2: 3 3 4

题目链接:http://code.google.com/codejam/contest/6214486/dashboard#s=p1

数据限制
1 <= ai <= 5000, 1 <= bi <= 5000

题目大意:统计经过某个公交站点的公交线路数量,即统计包含某个数字的区间个数。由于数据范围有限,可以用一个数组cntArr记录包含k的区间个数为cntArr[k]。比较暴力的做法是,从起点a到终点b,逐个遍历

for(int i=a; i<=b; i++) cntArr[i]++;

这里可以优化为

cntArr[a]++;   cntArr[b+1]–;

最后,在做一次统一的累加操作。

/**
 * Created by GaoTong on 2014/11/9.
 * copyright: www.acmerblog.com
 */
public class GBusCount {
    static Scanner s = null;
    static int n;
    static final int MAXN = 5005;
    static int cntArr[];

    public static void main(String args[]) throws FileNotFoundException {
        s = new Scanner(System.in);
        int c = s.nextInt();

        for(int k=1; k<=c; k++){
            int n = s.nextInt();
            cntArr = new int[MAXN];
            int minVal = MAXN;
            int maxVal = -1;
            for(int i=0; i<n; i++){
                int a = s.nextInt(); //the start station
                int b = s.nextInt(); //the end station
                if( minVal > a) minVal = a;
                if(maxVal < b) maxVal = b;
                cntArr[a]++;
                cntArr[b+1]--;
            }
            for(int i=1; i<=maxVal; i++)
                cntArr[i] += cntArr[i-1];

            int p = s.nextInt();
            System.out.print("Case #" + k + ":");
            while(p-- > 0){
                int point = s.nextInt();
                if( point < minVal || point > maxVal)  System.out.print(" 0");
                System.out.print(" " + cntArr[point]);
            }
            System.out.println();
        }
    }
}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  4. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.