AOJ 757.路边的树

138


题目



Description


长度为L的路边有一排树,相邻树间隔为1米,树种在整数点,0,1,2,….,L.
现在马路上有一些区域修地铁,区域用起点和终止点表示。已知有M个区域要修地铁,区间之间可能重合的部分。现要把这些区域(包括端点处的两棵数)移走
,计算些树移走后,马路上还有多少棵树。



Input


第一行有两个整数L(1<=L<=10000)和M(1<=M<=100),L代表马路的长度, M代表区域数。L和M之间用一个空格分隔开。接下来的M行,每行包含两个不同的
整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。



Output


输出包括一行,这一行只包含一个整数,表示马路上剩余的树的数目。



Sample Input


500 3
150 300
100 200
470 471



Sample Output


298


题解



用数组来模拟道路,先把所有位置种上树(TRUE),把需要砍掉的FALSE掉即可


代码



/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)

const int maxn = 10005;
bool tree[maxn];

bool Do() {
    int L,M;
    if(scanf("%d%d",&L,&M)==EOF)
        return false;

    memset(tree,true,sizeof(tree));

    REP(M) {
        int a,b;
        scanf("%d%d",&a,&b);
        for(int i = a;i <= b;i++)
            tree[i] = false;
    }

    int cnt = 0;
    for(int i = 0;i <= L;i++)
        if(tree[i])
            cnt++;
    

    printf("%d\n",cnt);
    return true;
}

int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论