校门外的树.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 
#include 
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
    }
    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>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;imax-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<哦哦  发布时间: 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[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}
        System.out.print(l+1-c);
        }    
    }
评论人: TheOnlyaaa  发布时间: 2013-3-21 23:05:52
#include 
#include 

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>begin[i]>>end[i];
        out<nt 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<ream>
using namespace std;
int main()
{
    int l,m,n;
    int a[100],b[100];
    int ta,tb;
    cout<<"请输入路的长度l："<>l;
    n=l+1;
    cout<<"请输入多少个区域："<>m;
    if(m<=0)
    {
        cout<"<>a[i]>>b[i];
    }
    for(i=0;ia[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;ib[i-1])
                n=n-(b[i]-b[i-1]);
            if(b[i]      }
        else
        {
            n=n-(b[i]-a[i]+1);
        }
    }
    cout<
void main()
{int n[101],m[101],a[10001]={0},i,k,l,j,s=0;
scanf("%d%d",&l,&k);
for(i=0;in[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
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;ip[j].start){
                temp=p[i];
                p[i]=p[j];
                p[j]=temp;
            }
        }
    for(i=0;iend>=p[i+1].start)
            p[i+1].start=p[i].end+1;
    }
}

void main(){
    int L,M,num=0;
    cout<<"请输入马路长度L和区域数目M："<>L>>M;
    cout<<"请输入各个区域的起始点坐标和终止点坐标："<>p[i].start>>p[i].end;
    }
    sort(p,M);
    for(i=0;i){
        num+=p[i].end-p[i].start+1;
    }
    cout<<"马路上剩余的树的数目为："<g[] 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=0i
                    a=a+t.inner(roadstart[i], roadend[i], roadstart[j+1], roadend[j+1]);
                }
            }
        }else{
            for(int i=0,j=0;i                    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(start1start2)
            return end2-start1;
        else if(start2       return end2-end1;
        else if(start2
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>erastart[i]>>eraend[i];
for (i=0;i
        tree[j]=0;
for (i=0;i<=count;i++)
    treenum+=tree[i];
cout<<"树的最终数目为：  "<
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 <答案是不是500 如果不是说明你错了
#include 
#include 
#include 
#include 
#include "string.h"
using namespace std;

class CPair
{
    public:
        int mFirst;
        int mSecond;
}
int getData( CPair* pair, const char* strFileName )
{
    ifstream is;
    isopen( 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 
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>a[i]>>b[i];
    for(i=0;i=a[i])&&(array[j]<=b[i]) )
            array[j]=-1;
        }
    }

    for(i=0;i<=count;i++)
    {if(array[i]!=-1)c++;}
    cout<<"还有"<
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;ii=0;i<=L;i++)
    if(trees[i]) count++;
    printf("%d\n",count);
    return 0;
}
评论人: xuke  发布时间: 2011-5-3 13:13:40
#include
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 {
        int begin,end;
        scanf("%d%d",&begin,&end);
        if(beginees[i]) count++;
    printf("%d\n",count);
    return 0;
}
评论人: beichenming  发布时间: 2011-5-1 16:51:25
帮忙看一下这个程序对吗？
#include 
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],&b[i]);
     sum=sum+(b[i]-a[i]+1);
   }
   for(i=0;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]           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
int cun(int m_[][2],int v,int a,int b){
    int i;
    for(i=0;i       if(bm_[i][0])a=m_[i][0];//把重叠的数整合
        if(b 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