游客 注册 | 登录
中文 | En

1763 - 校门外的树

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB 


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


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

<br />

题目输入


<span><span>输入文件</span><span><span><span>tree.in</span></span></span></span><span><span>的第一行有两个整数</span><span><span><span>L</span></span></span></span><span><span>（</span><span><span><span>1 &lt;= L &lt;= 10000</span></span></span></span><span><span>）和 </span><span><span><span>M</span></span></span></span><span><span>（</span><span><span><span>1 &lt;= M &lt;= 100</span></span></span></span><span><span>），</span><span><span><span>L</span></span></span></span><span><span>代表马路的长度，</span><span><span><span>M</span></span></span></span><span><span>代表区域的数目，</span><span><span><span>L</span></span></span></span><span><span>和</span><span><span><span>M</span></span></span></span><span><span>之间用一个空格隔开。接下来的</span><span><span><span>M</span></span></span></span><span><span>行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。</span></span>


<br />

题目输出


<span><span>输出文件</span><span><span><span>tree.out</span></span></span></span><span><span>包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。</span></span>


<br />

输入/输出样例

输入格式

500 3
150 300
100 200
470 471

输出格式

298

C++解答

#include <iostream>
#include <cmath>
using namespace std;
int l,m,s[101],t[101],left,right,sum=0;
int main()
{
    cin>>l>>m;
    for (int i=1;i<=m;i++) cin>>s[i]>>t[i];
    for (int j=2;j<=m;j++)
    {  
        for (int i=m;i>=j;i--) 
        {
          if (s[i]<s[i-1]) 
          {s[0]=s[i],s[i]=s[i-1],s[i-1]=s[0],
          t[0]=t[i],t[i]=t[i-1],t[i-1]=t[0];}
        }
    }
//    for (int i=1;i<=m;i++) cout<<s[i]<<" "<<t[i]<<endl;
    int left=s[1]; int right=t[1];
    for (int i=2;i<=m;i++)
    {
        if (s[i]<=right) {right=max(right,t[i]);}
        else 
        {sum+=right-left+1; left=s[i]; right=t[i];}
    }
    sum+=right-left+1;
    cout<<l-sum+1<<endl;
//    system ("pause");
    return 0;
}

Python解答

# coding=utf-8
l,m=map(int,input().split())
a=[]
s=["true"]*(l+1)
n=0
for i in range(m):
    b=list(map(int,input().split()))
    a.append(b)

for i in range(m):
    for j in range(a[i][0],a[i][1]+1):
        s[j]="false"

for k in s:
    if k=="true":
        n+=1
print(n)
请先登陆