洛谷P1047-校门外的树(模拟)

简介: 洛谷P1047-校门外的树(模拟)

题目描述:


某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是111米。我们可以把马路看成一个数轴,马路的一端在数轴000的位置,另一端在LLL的位置;数轴上的每个整数点,即0,1,2,…,L0,1,2,…,L0,1,2,…,L,都种有一棵树。


由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后,马路上还有多少棵树。


输入:


第一行有222个整数L(1≤L≤10000)L(1 \le L \le 10000)L(1≤L≤10000)和M(1≤M≤100) M(1 \le M \le 100)M(1≤M≤100),LLL代表马路的长度,MMM代表区域的数目,LLL和MMM之间用一个空格隔开。

接下来的MMM行每行包含222个不同的整数,用一个空格隔开,表示一个区域的起始点和终止点的坐标。


输出:  


1个整数,表示马路上剩余的树的数目。


样例输入:


500 3

150 300

100 200

470 471


样例输出:


298


说明/提示:


NOIP2005普及组第二题

对于2020%20的数据,区域之间没有重合的部分;

对于其它的数据,区域之间有重合的情况。


程序代码:


#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 10001
int x[N];
int main()
{
    int l,m,sum,a,b,i,j;
    cin>>l>>m;
  memset(x,0,sizeof(x));
    for(i=1;i<=m;i++)
  {
    cin>>a>>b;
    for(j=a;j<=b;j++)
    {
      x[j]=1;
    }
  }
  for(i=0;i<=l;i++)
  {
    if(x[i]==0)
      sum++;
  }
  cout<<sum<<endl;
  return 0;
}
相关文章
|
19天前
lanqiao OJ 131 生命之树
lanqiao OJ 131 生命之树
28 0
|
20天前
lanqiao oj 131 生命之树
lanqiao oj 131 生命之树
26 0
|
6月前
|
机器学习/深度学习 Java Python
代码解密 | 2024春晚刘谦魔术与约瑟夫环问题
2024春节联欢晚会中,刘谦老师的魔术节目可以说是我心目中的全场最佳~春晚刚结束网上就有大佬给出了第二个魔术(拼扑克牌)的数学模拟,也有大佬发布了代码程序。博主在模拟了魔术过程之后,也在此分享一下程序代码和思路。同时,也借此回顾一下经典的数学问题:约瑟夫环问题。
94 8
|
5月前
|
人工智能 程序员 定位技术
老程序员分享:NOIP2016天天爱跑步(树上差分)
老程序员分享:NOIP2016天天爱跑步(树上差分)
28 0
|
6月前
【错题集-编程题】过河卒(动态规划-路径问题)
【错题集-编程题】过河卒(动态规划-路径问题)
|
6月前
【编程题-错题集】kotori和气球(组合数学)
【编程题-错题集】kotori和气球(组合数学)
|
12月前
|
算法 测试技术 容器
代码随想录算法训练营第四十二天 | LeetCode 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零
代码随想录算法训练营第四十二天 | LeetCode 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零
43 1
|
12月前
|
算法
代码随想录算法训练营第三十二天 | LeetCode 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II
代码随想录算法训练营第三十二天 | LeetCode 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II
46 0
|
测试技术
蓝桥 晚会节目单 (线段树)
蓝桥 晚会节目单 (线段树)
【每日一道智力题】之如何最快的找到最轻的砝码
【每日一道智力题】之如何最快的找到最轻的砝码
200 0