G Bus Count (Google Kickstart2014 Round D Problem B) (DAY 89)

1：题目

Some cities are built along a straight road.

The cities are numbered from left to right 1,2,3…
有 N 个 G Buses run on this road.

对于每个 G 巴士,We know the city limits it serves：第 i 个 g The bus is numbered Ai 和 Bi 之间的城市（包含 Ai 和 Bi）提供服务.

Now given you a subset of cities P.

对于 P for each city included,We need to find out how many cars there are G Buses serve the city.

输入格式
第一行包含整数 T,表示共有 T 组测试数据.

每组数据第一行包含整数 N,表示 G number of buses.

第二行包含 2N 个整数,形式为 A1 B1 A2 B2 A3 B3…AN BN,其中第 i 个 G The bus service is numbered from Ai 到 Bi（包括）的城市.

第三行包含整数 P,Indicates the number of cities queried.

接下来 P 行,每行包含一个整数 Ci,Indicates the number of a query city.

A blank line precedes each set of data.

输出格式
每组数据输出一个结果,每个结果占一行.

结果表示为 Case #x: y,其中 x 是组别编号（从 1 开始）,y 是 P 个空格隔开的整数,其中第 i The integers are for the city Ci 提供服务的 G number of buses.

数据范围
1≤T≤10,
1≤N≤500,
1≤Ai,Bi,Ci≤5000,
1≤P≤500
输入样例：
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
输出样例：
Case #1: 2 1
Case #2: 3 3 4
样例解释
在样例＃1中,有四个 G 巴士.

The first service city 15 到 25,The second service city 30 到 35,The third service city 45 到 50,The fourth service city 10 到 20.

城市 15 by the first and fourth G bus service,城市 25 Only by the first one G bus service,So the answer output is 2 1.

2:代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010;

int n, m;
int b[N];

int main()
{
    
    int T;
    scanf("%d", &T);
    for (int cases = 1; cases <= T; cases ++ )
    {
    memset
        (b, 0, sizeof b);
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
    
            int l, r;
            scanf("%d%d", &l, &r);
            b[l] ++ , b[r + 1] -- ;
        }
        for (int i = 1; i < N; i ++ ) b[i] += b[i - 1];
        scanf("%d", &m);

        printf("Case #%d: ", cases);
        while (m -- )
        {
    
            int x;
            scanf("%d", &x);
            printf("%d ", b[x]);
        }
        puts("");
    }

    return 0;
}