校门外的树.doc

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

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

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

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

【样例输入】
500 3

150 300

100 200

470 471

【样例输出】
298

【数据规模】
对于20%的数据，区域之间没有重合的部分；
对于其它的数据，区域之间有重合的情况。
来源：
最新评论发表评论
您尚未登录本站，不能发表评论，请登录 或者 注册 成为本站会员
评论人: zoobyz  发布时间: 2013-3-25 19:07:24
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
    int start_L;
    int end_L;
}tree[10001];
int cmp(node x,node y)
{
    if(x.start_L!=y.start_L)
    {
        return x.start_L<y.start_L;
    }
    else
    return x.end_L>y.end_L;
}
int main()
{
    int M,N,min,max,i;
    ifstream in("treeIn.txt");
    ofstream out("treeOut.txt");
    in>>M>>N;
    for(i=0;i<N;i++)
    {
        in>>tree[i].start_L>>tree[i].end_L;
        if(tree[i].start_L>tree[i].end_L)
        tree[i].start_L^=tree[i].end_L^=tree[i].start_L^=tree[i].end_L;
    }
    sort(tree,tree+N,cmp);
    for(min=0,max=0,i=0;i<N;i++)
    {
        if(i==0)
        {
            min=tree[i].start_L;
            max=tree[i].end_L;
        }
        if(max<tree[i].start_L)
        {
            M-=(max-min+1);
            min=tree[i].start_L;
            max=tree[i].end_L;
        }
        else if(max>=tree[i].start_L)
        {
            if(tree[i].end_L>max)
            max=tree[i].end_L;
        }
    }
    out<<M-(max-min)<<endl;
    return 0;
}
还可以比这个复杂度更低么？求教
评论人: 小江湖哦哦  发布时间: 2013-3-24 21:49:31
Java 的简单实现，我想应该是最简便的了！！
import java.util.Scanner;

public class tree {

    public static boolean pans(int load[][],int k){
        for(int i=0;i<load.length;i++){
        if(k>=load[i][0]&&k<=load[i][1])
                return true;
        }
        return false;        
    }

    public static void main(String[] args) {
        int l,m;
        int c=0;
        Scanner input=new Scanner(System.in);
          System.out.println("输入马路长度，区域数目");
        l=input.nextInt();
        m=input.nextInt();
        int load[][]=new int[m][2];
        System.out.println("输入马路的坐标");
        for(int i=0;i<load.length;i++){
            for(int j=0;j<2;j++)
            load[i][j]=input.nextInt();
        }
        System.out.println("输入完毕");
        for(int i=0;i<=500;i++){
            if(pans(load,i))
                ++c;    
            }
        System.out.print(l+1-c);
        }    
    }
评论人: TheOnlyaaa  发布时间: 2013-3-21 23:05:52
#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    int M,N;
    ifstream in("treeIn.txt");
    ofstream out("treeOut.txt");
    in>>M>>N;

    int *tree=new int[M+1];
    int *begin=new int[N];
    int *end=new int[N];
    for(int i=0;i<=M;i++)
        tree[i]=0;
    for(int i=0;i<N;i++)
    {
        in>>begin[i]>>end[i];
        out<<begin[i]<<" "<<end[i]<<endl;
    }
    in.close();
    in.clear();

    for(int i=0;i<N;i++)
        for(int j=begin[i];j<=end[i];j++)
            if(!tree[j])
                tree[j]=1;

    int num=0;
    for(int i=0;i<=M;i++)
        if(!tree[i])
            ++num;

    out<<num;
    out.close();
    out.clear();

    return 1;
}
评论人: chuck_强仔  发布时间: 2012-4-13 15:05:22
#include<iostream>
using namespace std;
int main()
{
    int l,m,n;
    int a[100],b[100];
    int ta,tb;
    cout<<"请输入路的长度l："<<endl;
    cin>>l;
    n=l+1;
    cout<<"请输入多少个区域："<<endl;
    cin>>m;
    if(m<=0)
    {
        cout<<n<<endl;
        return 0;
    }
    cout<<"请输入每个区域的起始点和终点并以空格分开："<<endl;
    for(int i=0;i<m;i++)
    {
        cin>>a[i]>>b[i];
    }
    for(i=0;i<m-1;i++)
    {
        for(int j=1;j<m;j++)
        {
            if(a[i]>a[j])
            {
                ta=a[i];
                a[i]=a[j];
                a[j]=ta;
                tb=b[i];
                b[i]=b[j];
                b[j]=tb;
            }
        }
    }
    n=n-(b[0]-a[0]+1);
    for(i=1;i<m;i++)
    {
        if(a[i]<=b[i-1])
        {
            if(b[i]>b[i-1])
                n=n-(b[i]-b[i-1]);
            if(b[i]<b[i-1])
                b[i]=b[i-1];
        }
        else
        {
            n=n-(b[i]-a[i]+1);
        }
    }
    cout<<n<<endl;
    return 0;
}
评论人: qq379666774  发布时间: 2012-4-5 14:54:15
#include<stdio.h>
void main()
{int n[101],m[101],a[10001]={0},i,k,l,j,s=0;
scanf("%d%d",&l,&k);
for(i=0;i<k;i++){ 
 scanf("%d%d",&n[i],&m[i]);
  for(j=n[i];j<=m[i];j++) if(!a[j]) a[j]=1;
}
for(i=0;i<=l;i++) s=s+a[i];
printf("%d\n",l+1-s);
}
评论人: trhuo  发布时间: 2012-3-30 19:12:17
#include<iostream>
using namespace std;
struct domain{
    int start;
    int end;
}p[10];

void sort(struct domain p[],int n){//对各个区域按起点坐标从小到大排序
    struct domain temp;
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++){
            if(p[i].start>p[j].start){
                temp=p[i];
                p[i]=p[j];
                p[j]=temp;
            }
        }
    for(i=0;i<n-1;i++)//消除重叠部分
    {
        if(p[i].end>=p[i+1].start)
            p[i+1].start=p[i].end+1;
    }
}

void main(){
    int L,M,num=0;
    cout<<"请输入马路长度L和区域数目M："<<endl;
    cin>>L>>M;
    cout<<"请输入各个区域的起始点坐标和终止点坐标："<<endl;
    for(int i=0;i<M;i++){
        cin>>p[i].start>>p[i].end;
    }
    sort(p,M);
    for(i=0;i<M;i++){
        num+=p[i].end-p[i].start+1;
    }
    cout<<"马路上剩余的树的数目为："<<L+1-num<<endl;

}
评论人: yangzzu  发布时间: 2011-11-25 0:12:05
用语言届的帝王语言：
package treeOutofSchool;

import java.util.Scanner;

public class Tree {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int roadlength=sc.nextInt();
        int railaylength=sc.nextInt();
        int roadstart[] = new int[railaylength],roadend[] = new int[railaylength];
        int a=0;
        for(int i=0;i<railaylength;i++){
            roadstart[i]=sc.nextInt();
            roadend[i]=sc.nextInt();
        }
        if(railaylength%2==0){
            for(int i=0,j=0;i<railaylength&&j<railaylength-1;i++,j++){
                if(roadstart[i]<roadend[i]){
                    Tree t=new Tree();
                    a=a+t.inner(roadstart[i], roadend[i], roadstart[j+1], roadend[j+1]);
                }
            }
        }else{
            for(int i=0,j=0;i<railaylength-1&&j<railaylength-2;i=i+2){
                if(roadstart[i]<roadend[i]){
                    Tree t=new Tree();
                    a=a+t.inner(roadstart[i], roadend[i], roadstart[j+1], roadend[j+1]);
                }
            }
        }
        if(railaylength%2==0)
            System.out.println(roadlength-a-1);
        else
            System.out.println(roadlength-a-(roadend[railaylength-1]-roadstart[railaylength-1])-1);
    }
    public int inner(int start1,int end1,int start2,int end2){
        if(start1<start2&&end1>start2)
            return end2-start1;
        else if(start2<start1&&end2<start1)
            return end1-start2;
        else if(start1<start2&&end1<end2)
            return end2-end1;
        else if(start2<start1&&end2<end1)
            return end1-start2;
        else
            return end1-start1+end2-start2;
    }
}
评论人: wangyueren1101  发布时间: 2011-11-18 13:57:06
#include <iostream>
using namespace std;
void main()
{
int tree[1000],erastart[100],eraend[100];
int count,eran,i,treenum=0;//count 树的数目,eran区域个数
cout<<"树的终点值及树的区域个数\n";
cin>>count>>eran;
for (i=0;i<=count;i++)//初始化为1
tree[i]=1;
cout<<"输入区域的起始点\n";
for (i=0;i<eran;i++)
    cin>>erastart[i]>>eraend[i];
for (i=0;i<eran;i++)
    for(int j=erastart[i];j<=eraend[i];j++)
        tree[j]=0;
for (i=0;i<=count;i++)
    treenum+=tree[i];
cout<<"树的最终数目为：  "<<treenum<<endl;
system("pause");
}
评论人: thefoxofsky  发布时间: 2011-11-3 15:40:15
样例有误 应该输出297才对！

下面是代码

#include<iostream>
using namespace std;

int main ()
{
    int tree, n, special = 0;
    cin >> tree >> n;
    int * p = NULL;

    do                            //分配动态数组
    {
        p = new int [2 * n];
    }while(p != NULL);

    int a  = n;

    for (int i =0 ;i < 2*a ; i++)  //初始化数组
    {
        p[i] = 0;
    }

    for (int i =0 ;i < a ; i++)
    {
        cout << "请输入第" << i+1 << "个区间（先小后大）：";
        cin >> p[i] >> p[n+i];
        if ( p[i]==0 )
        {
            special = 1;
        }

        if(i)
        {
            if( p[i] <= p[i-1] && p[n+i] >= p[n+i-1])
            {
                p[i-1] = p[i];
                p[i] = 0;
                p[n+i-1] = p[n+i];
                p[n+1] = 0;
                a = a - 1;
                i = i - 1;
            }

            if( p[i] >= p[i-1] && p[n+i] <= p[n+i-1])
            {
                p[i] = 0;
                p[n+1] = 0;
                a = a - 1;
                i = i - 1;
            }

            if( p[i] <= p[i-1] && p[n+i] >= p[i-1] && p[n+i] <= p[n+i-1])
            {
                p[i-1] = p[i];
                p[i] = 0;
                p[n+i] = 0;
                a = a - 1;
                i = i - 1;
            }

            if( p[i] >= p[i-1] && p[i] <= p[n+i-1] && p[n+i] >= p[n+i-1])
            {
                p[n+i-1] = p[n+i];
                p[i] = 0;
                p[n+i] = 0;
                a = a - 1;
                i = i - 1;
            }
        }//end the first if
    }//end for

    int cut = 0;
    for (int i = 0; i < a; i++)
    {
        cut = cut + (p[n+i] - p[i] + 1);
    }

    tree = tree - cut + special;
    cout << tree <<endl;
    system("pause");
}
评论人: snakezzz  发布时间: 2011-10-26 11:06:12
飘渺 答案没有错误 
你把
500 1
500 500
代入 看看你的答案是不是500 如果不是说明你错了
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include "string.h"
using namespace std;

class CPair
{
    public:
        int mFirst;
        int mSecond;
}
int getData( CPair* pair, const char* strFileName )
{
    ifstream is;
    is.open( strFileName );
    stringstream strs( stringstream::in | stringstream::out );
    string st;
    int n;
    while( getline(is ,st) )
    {
        strs << st;
    }
    int x = 0;
    int y = 0;
    while( strs >> n )
    {
        if( x%2 == 0 )
        {
            pair->mFirst = n;
        }
        else
        {
            pair->mSecond = n;
            pair++;
        }
        x++;
    }
    return n;
}
int main()
{
    const char* str = "tree.in";
    CPair* pair = new CPair[10];
    memset( pair, 0, 10*sizeof(CPair) );
    CPair* p = pair;
    getData( pair, str );
    const int MAX = p->mFirst;
    int j = 0;
    int i = 0;
    int array[MAX];
    memset( array, 0, MAX*sizeof(int) );
    int loop = p->mSecond;
    for( j = 0; j < loop; ++j )   zzz   
    {
        p++;
        for( i = p->mFirst; i <= p->mSecond; ++i )
        {
            array[i] = 1;
        }
    }
    int x = 0;
    for(int i = 0; i <= MAX; ++i)
    {
        if( array[i] == 0 )
            x++;
    }
    cout << x << endl;
    delete[] pair;
}
评论人: pan923927  发布时间: 2011-10-19 14:39:13
#include <iostream>
using namespace std;

int main()
{
    int array[1001];
    int a[100];
    int b[100];    //数组a b分别记录所分区域的起始坐标
    int count,counter;//count表示最后一个数对应的坐标，counter表示将分几部分
    int c=0;        //c用于统计剩余的树有多少课
    int i;
    cout<<"输入马路长度和划分区域数目\n";
    cin>>count>>counter;

    for(i=0;i<=1000;i++)//将数组初始化为-1
        array[i]=-1;
    for(i=0;i<=count;i++)//用循环为数组赋值
        array[i]=i;
    for(i=0;i<counter;i++)
        cin>>a[i]>>b[i];
    for(i=0;i<counter;i++)
    {
        for(int j=0;j<=count;j++)
        {    
            if( (array[j]>=a[i])&&(array[j]<=b[i]) )
            array[j]=-1;
        }
    }

    for(i=0;i<=count;i++)
    {if(array[i]!=-1)c++;}
    cout<<"还有"<<c<<"棵树\n";

}
评论人: xuke  发布时间: 2011-5-3 13:14:37
#include<stdio.h>
int main()
{
    int L,i,j,n;
    bool trees[10001];
    for(i=0;i<10001;i++)
        trees[i]=true;
    scanf("%d%d",&L,&n);
    for(i=0;i<n;i++)
    {
        int begin,end;
        scanf("%d%d",&begin,&end);
        if(begin<end)
            for(j=begin;j<=end;j++)
                  trees[j]=false;
        else
            for(j=end;j<=begin;j++)
                trees[j]=false;
    }
    int count=0;
    for(i=0;i<=L;i++)
    if(trees[i]) count++;
    printf("%d\n",count);
    return 0;
}
评论人: xuke  发布时间: 2011-5-3 13:13:40
#include<stdio.h>
int main()
{
    int L,i,j,n;
    bool trees[10001];
    for(i=0;i<10001;i++)
        trees[i]=true;
    scanf("%d%d",&L,&n);
    for(i=0;i<n;i++)
    {
        int begin,end;
        scanf("%d%d",&begin,&end);
        if(begin<end)
            for(j=begin;j<=end;j++)
                  trees[j]=false;
        else
            for(j=end;j<=begin;j++)
                trees[j]=false;
    }
    int count=0;
    for(i=0;i<=L;i++)
    if(trees[i]) count++;
    printf("%d\n",count);
    return 0;
}
评论人: beichenming  发布时间: 2011-5-1 16:51:25
帮忙看一下这个程序对吗？
#include <stdio.h>
int main(void)
{
 int a[100],b[100];
 int n,m,sum,i,j;
 while(scanf("%d %d",&n,&m)!=EOF)
 {
     sum=0;
  for(i=0;i<m;i++)
   {
     scanf("%d %d",&a[i],&b[i]);
     sum=sum+(b[i]-a[i]+1);
   }
   for(i=0;i<m;i++)
     for(j=0;j<m;j++)
    {
       if(i==j)
        continue;
       else
          if(a[i]<=b[j]&&a[i]>=a[j]&&b[i]>=b[j])
              sum=sum-(b[j]-a[i]+1);
        else
          if(a[i]<=b[j]&&a[i]>=a[j]&&b[i]<b[j])
              sum=sum-(b[i]-a[i]+1);
    }
    printf("%d\n",n+1-sum);
 }
  return 0;
}

评论人: longgui0318  发布时间: 2011-3-20 21:28:36
我的错了 能帮我看下是哪错了吗 我看不出来
评论人: longgui0318  发布时间: 2011-3-20 21:28:00
#include<stdio.h>
int cun(int m_[][2],int v,int a,int b){
    int i;
    for(i=0;i<v;i++){
        if(b<m_[i][0])continue;//区域重叠判断
        if(m_[i][1]<a)continue;//区域重叠判断
        if(a>m_[i][0])a=m_[i][0];//把重叠的数整合
        if(b<m_[i][1])b=m_[i][1];//把重叠的数整合
        m_[i][0]=0;m_[i][1]=0;}//经整合后此数组归零
    m_[v][0]=a;//把整合的数存到数组
    m_[v][1]=b;//把整合的数存到数组
    return v+1;}//返回当前数组长度
int main(){
    int l,m,m_[100][2],a,b,t,vale=0,k=0;
    scanf("%d%d",&l,&m);
    while(m--){
        scanf("%d%d",&a,&b);
        if(a>b){t=a;a=b;b=t;}//大小调整
        vale=cun(m_,vale,a,b);}
    for(t=0;t<vale;t++)
    if(m_[t][1]!=m_[t][0])k=k+1+m_[t][1]-m_[t][0];
    k=l+1-k;
    printf("%d