首页 > 试题广场 >

剩下的树

[编程题]剩下的树
  • 热度指数:24215 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
    有一个长度为整数L(1<=L<=10000)的马路,可以想象成数轴上长度为L的一个线段,起点是坐标原点,在每个整数坐标点有一棵树,即在0,1,2,...,L共L+1个位置上有L+1棵树。     现在要移走一些树,移走的树的区间用一对数字表示,如 100 200表示移走从100到200之间(包括端点)所有的树。     可能有M(1<=M<=100)个区间,区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。

输入描述:
    两个整数L(1<=L<=10000)和M(1<=M<=100)。
    接下来有M组整数,每组有一对数字。


输出描述:
    可能有多组输入数据,对于每组输入数据,输出一个数,表示移走所有区间的树之后剩下的树的个数。
示例1

输入

500 3
100 200
150 300
470 471

输出

298
#include<bits/stdc++.h>
using namespace std;
int vis[10001];

void CHU(int from,int to){
    for(int i=from;i<=to;i++){
        vis[i]=1;
    }
    return;
}

int main(){
    int L,M;
    while(cin>>L>>M){
        int from,to;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<M;i++){
            cin>>from>>to;
            CHU(from,to);
        }
        int ans=0;
        for(int i=0;i<=L;i++){
            if(vis[i]==0){
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2021-09-01 23:48:28 回复(0)
一个数组问题,但是发现一个坑,c语言中const的用法
c中的const不是一个真正的常量,更像一个只读标识符
所以不能用来作为数组初始化的大小
//设置一个数组,布尔数组或者int数组都可

#include <stdio.h>
#include <stdbool.h>


//不能const
bool arr[10001];

int main(){
    int l,m,count,x,y;
    scanf("%d%d",&l,&m);
    for(int i=0;i<l;i++){
        arr[i]=true;//种树
    }
    count=l+1;
    while(m--){
        scanf("%d%d",&x,&y);
        for(int j=x;j<=y;j++){
            if(arr[j]){
                arr[j]=false;
                count--;
            }
        }
    }
    printf("%d",count);
}


发表于 2021-03-18 16:07:28 回复(0)
跟大部分的人都差不多,小白也能看懂,定义一个数组,注意点是数组的大小务必得是L+1,比如说L=100,那么就有101棵树!
#include<iostream>
using namespace std;

int main(){
    int l,m;
    int from,to;//区间
    while(cin >> l >> m){
        //判断
        if(l > 10000 || m > 100) break;
        //正文
        int arr[l + 1];
        for(int i = 0; i <= l; i++){
            arr[i] = 1;
        }
        for(int i = 0; i < m; i++){
            cin >> from >> to;
            for(int j = 0; j <= to - from; j++){
                arr[from - 1 + j] = 0;
            }
        }
        int residual = 0; //剩余
        for(int i = 0; i <= l; i++){
            if(arr[i] == 1)
                residual++;
        }
        cout << residual << endl;
    }
    return 0;
}





发表于 2021-03-12 10:23:30 回复(0)
看了大家伙的回答,时间复杂度基本都是L级别的。这里我写了个m级别的,希望对大家有帮助
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool cmp(vector<int>a,vector<int>b)
{
    if(a[0]==b[0])
        return a[1]<b[1]; //区间左边界相等,则右边界小的排在前
    return a[0]<b[0]; //区间左边界小,则排在前
}

int main() //即求所有区间的并集
{
    int L,m;
    while(scanf("%d %d",&L,&m)!=EOF)
    {
        vector<vector<int> >nums(m,vector<int>(2)); //存储区间
        for(int i=0;i<m;i++)
            scanf("%d %d",&nums[i][0],&nums[i][1]);
        sort(nums.begin(),nums.end(),cmp); //排序
        int sum=0,left=1,right=0;
        for(int i=0;i<nums.size();i++) //类似于合并区间
        {
            if(nums[i][0]>right) //前后区间不相交
            {
                sum+=right-left+1; //加上前面的累积
                left=nums[i][0];
                right=nums[i][1]; //更新
            }
            else
                right=max(right,nums[i][1]);
        }
        sum+=right-left+1; //共有sum树被移走
        int res=L-sum+1;
        printf("%d\n",res);
    }
}



编辑于 2020-04-05 21:38:43 回复(0)
#include<stdio.h>//初始化有树的位置为-1  无树的位置为0, 计算-1的个数及树木的个数
int main()
{
    int n,m,a,b,i,j,tree[10000],num=0;
    scanf("%d%d",&n,&m);
    //初始化,注意用memset初始化时只可以初始化为0或者-1  并且别忘记本题的长度为L+1
    memset(tree, -1, sizeof(int) * (n+1));
    for(i=1;i<=m;i++)//减去树木
    {
        scanf("%d%d",&a,&b);
        for(j=a;j<=b;j++)
            tree[j]=0;
    }
    for(i=0;i<=n;i++)//计算剩余树木
        if(tree[i]==-1) 
            num++;
    printf("%d",num);
}

发表于 2020-03-23 20:00:49 回复(0)
建立一个全是1的数组,然后把区间上的值清零,最后统计1个个数。本来以为这么做会超时,还是AC了。

#include<iostream>
using namespace std;
int main(){
	int a[10001];
	int L,M;
	while(cin>>L>>M){
		for(int i=0;i<=L;i++){
			a[i]=1;
		}
		int begin[100],end[100];
		for(int i=0;i<M;i++){
			cin>>begin[i]>>end[i];
		}
		for(int i=0;i<M;i++){
			for(int j=begin[i];j<=end[i];j++){
				a[j]=0;
			}
		}
		int sum=0;
		for(int i=0;i<=L;i++){
			if(a[i]==1){
				sum++;
			}
		}
		cout<<sum<<endl;
	}
	return 0;
}


发表于 2020-03-19 11:52:11 回复(0)
#include <bits/stdc++.h>
 
using namespace std;
int has[10005];
int main(){
    int n,m;
    while(cin>>m>>n){
        memset(has,0,sizeof has);
        for(int i=0;i<n;i++){
            int a,b;
            cin>>a>>b;
            has[a]++,has[b+1]--;
        }
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            has[i]+=has[i-1];
            if(has[i-1]==0)
                ans++;
        }
        if(has[m]==0) ans++;
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2019-08-13 23:53:17 回复(0)
    #include <math.h>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int main(){
        int L,M,t1,t2,*a;
        while(scanf("%d%d",&L,&M)){
            a = (int *)malloc(sizeof(int)*(L+1));
            for(int i=0;i<=L;a[i++]=0);        
            for(int i=0;i<M;i++){
                scanf("%d%d",&t1,&t2);
                for(;t1<=t2;a[t1++]=1);
            }
            int count = 0;
            for(int i=0;i<=L;i++){
                if(!a[i]){
                    count++;
                }
            }
            printf("%d\n",count); 
        } 

        return 0; 
    }

我想知道这段代码哪里错了,为什么一直报超出了限制的内存?

发表于 2018-08-27 09:48:00 回复(4)
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>


#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>      //rand ( ), srand ( )
#include <ctime>        //time ( )

using namespace std;
char arr[10001];
int main ( )
{
    int L, M, a, b;
    while ( cin >> L >> M )
    {
        memset ( arr, 1, sizeof ( arr ) );
        while ( M -- )
        {
            cin >> a >> b;
            memset ( arr + a, 0, b - a + 1 );
        }
        int ans = 0;
        for ( int i = 0; i <= L; i ++ )
        {
            if ( arr[i] )
                ans ++;
        }
        cout << ans << endl;
    }
    return 0;
}

发表于 2018-03-04 16:53:38 回复(0)

这道题基本用一个数组就行了,大家代码都一样。
我来分享一个我踩到的坑,我的代码一开始是这样的:

int road[10001];
int main()
{
    while (cin >> L >> M)
    {
        memset(road, 1, sizeof(int) * L);
        //....
    }
}

之前也有用过 memset,没想到这次居然踩到坑了,这个代码运行是不成功的,因为 memset(road, 1, sizeof(int) * L); 并不会把 arr 数组变成 1。我在查看时发现所有的元素都变成了 16843009

这***的就很见鬼了,我一开始还以为是系统的 bug 后来查了一下资料才发现是我对 memset 理解的错误。

memset(数组名, 值, sizeof(数组名));

因为memset是按字节赋值,对每个字节赋值同样的值,这样int四个字节会附相同的值(这也是它为什么是在 cstring 里的原因)。而0二进制代码全为0,不容易错。

那么赋值为 1 时呢?你看啊,一个 int 四个四节,每个字节变成 1,那就是:

00000001 00000001 00000001 00000001

转换成10进制也就是16843009。
以后用 memset 的时候就要注意了,一般拿它来置零就行了,要想赋值为别的值,就用 algorithm 里的 fill吧。

void fill (ForwardIterator first, ForwardIterator last, const T& val);

当然这个会稍微慢一点。

发表于 2019-06-02 22:15:42 回复(4)
建立一个全是1的数组,移除了就清零,最后统计1的个数,搞定
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int L, M;
	while (cin >> L >> M)
	{
		vector<int> data(L + 1, 1);
		int start, end, cnt = 0;
		for (int i = 0; i < M; i++)
		{
			cin >> start >> end;
			for (int i = start; i <= end; i++)
				data[i] = 0;
		}
		for (vector<int>::iterator it = data.begin(); it != data.end(); it++)
			if (*it == 1)
				cnt++;
		cout << cnt << endl;
	}
	return 0;
}

发表于 2017-04-14 15:29:00 回复(11)
巧用memset。
#include <bits/stdc++.h>
using namespace std;
char v[10001];
int main(){
    for(int L,M,c;cin>>L>>M;){
        memset(v,1,L+1);
        for(int i,j;M-- &&cin>>i>>j;memset(&v[i],0,j-i+1));
        for(int i=c=0;i<=L;c+=(v[i++]?1:0));
        cout<<c<<endl;
    }
    return 0;
}

编辑于 2016-09-01 13:05:30 回复(4)
怎么算出来是298的?我按照题目的理解包括端点的话,算出来是500-(300-100+1)-(471-470+1)=297
发表于 2017-01-24 11:48:00 回复(4)
发现大家都是用的散列的方法,但是中间将区间置1的时候需要一个个遍历,复杂度太高了,数据如果刁钻一点完全过不了,所以我的方法是先将区间按左区间排序,然后在一个个访问减去区间值,对区间重合的只要小心处理就可以了
#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
class tree{
public:
    int left,right;
    bool operator < (const tree &b){
        return left<b.left;
    }
};
int main(){
    int n,m;
    while(cin>>n>>m){
        vector<tree> v(m);
        for(int i=0;i<m;++i)
            cin>>v[i].left>>v[i].right;
        sort(v.begin(),v.end());
        int cnt=n+1;
        int last=0;
        for(int i=0;i<m;++i)
            if(v[i].left>=last){
                cnt-=v[i].right-v[i].left+(v[i].left!=last);
                last=v[i].right;
            }
            else{
                if(v[i].right>last){
                    cnt-=v[i].right-last;
                    last=v[i].right;
                }
            }
        cout<<cnt<<endl;
    }
    
}






发表于 2019-03-05 21:33:58 回复(1)
其实很简单,是我想的太复杂了,开始想的交叉区间的方式对区间进行更新,但是需要多种分类讨论,而且容易重复或者漏掉,直接利用把所有树用一个数组存储,如果拔掉就置零的方式实现简单方便且逻辑清晰。
#include<iostream>
using namespace std;
int main() {
    int l, m;
    cin >> l >> m;
    int a[100][2];
    int* tree=new int[l+1];
    for (int i = 0; i<m; i++) {
        cin >> a[i][0] >> a[i][1];
    }
    int count = 0;
    for (int i = 0; i<=l; i++)
        tree[i]=1;
    for (int i = 0; i<m; i++){
        for(int j=a[i][0];j<=a[i][1];j++){
            tree[j]=0;
        }
    }
    int total = 0;
    for (int i = 0; i<=l; i++) {
        if(tree[i]!=0)
            total++;
    }
    cout << total << endl;
}

发表于 2019-02-07 08:48:18 回复(2)
用了散列的想法,其实和讨论中其他人的思想差不多,比如我只是没有用meset函数去赋值。也是
每次输入区间的时候就开始计算砍的树木,看过了就吧hash数组里面的0改为1标记一下,下次再遇到
重复区间,就不用再计数了,我自己觉得有个缺点就是,每次我都必须遍历区间里面的每一个点,
很浪费时间。(2019考研复试一定要上岸!)
#include<stdio.h>
int main()
{
    int L,m;
    while(scanf("%d",&L)!=EOF)
    {
        scanf("%d",&m);
        int hashTable[10000]={0};
        int a[10000][2],i,j;
        int sum=0;
        for(i=0;i<m;++i)
        {
            scanf("%d%d",&a[i][0],&a[i][1]);
            for(j=a[i][0];j<=a[i][1];++j)
            {
                if(hashTable[j]!=1)
                {
                    sum++;
                    hashTable[j]=1;
                }
            }
        }
        printf("%d\n",L-sum+1);
    }
    return 0;
}

发表于 2019-03-02 16:07:57 回复(0)
#include<stdio.h>
int main()
{
    int L,M,i,a[100],b[100],c[10001],k,j,count;
    while(scanf("%d%d",&L,&M)!=EOF)
    {
        count=L+1;
        for(i=0;i<M;i++)
        scanf("%d %d",&a[i],&b[i]);
        for(i=0;i<=L;i++)
            c[i]=1;
        for(i=0;i<M;i++)
            for(j=a[i];j<=b[i];j++)
            if(c[j]==1)
            {
                c[j]=0;
                count--;
            }
            printf("%d\n",count);
    }
    return 0;
}
发表于 2018-02-27 15:16:42 回复(0)
Java 解法
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int l = scanner.nextInt();
        int m = scanner.nextInt();
        int[] record = new int[l + 1];
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            for (int j = x; j <=y ; j++) {
                record[j]=1;
            }
        }
        int count=0;
        for (int i = 0; i <= l; i++) {
            if (record[i]==0)
                count++;
        }
        System.out.println(count);
    }
}


发表于 2020-03-07 21:53:18 回复(0)
思路:用初始值为0的数组,先0-L值区间“种树”置1,再拔掉m个区间内的树,即置0,最后将数组的各值加和即为剩余。
#include<iostream>
#include<cstring>
using namespace std;
int T[10001] = { 0 };//用数组储存
int fun1(int L) {
	for (int i = 0; i <= L; i++) {
		T[i] = 1;
	}
	return 0;
	//L区间内的树置为1
}
int fun2(int m) {
	int n1, n2;
	for (int i = 0; i < m; i++) {
		cin >> n1 >> n2;
		for (int i = n1; i <= n2; i++) {
			T[i] = 0;
		}
	}
	return 0;
	//拔掉的m个区间内的树置为0
}
int main() {
	int sum = 0;
	int L;
	int m;
	while (cin >> L >> m) {
		fun1(L);
		fun2(m);
		for (int i = 0; i <= L; i++) {
			sum += T[i];
		}
		cout << sum << endl;
		sum = 0;//注意输出完成后将结果再次置0
	}
}

发表于 2020-02-17 11:48:07 回复(0)
看到大家的回答深受启发,用bool值来表示树的存在与否,然后遍历区间段,将原有的true砍树成false,每少一棵树,总数-1
#include<iostream>
#include<cstdio>
using namespace std;
const int Maximum = 10001;
bool road[Maximum];
int main(){
    int length,CaseNum;
    scanf("%d%d",&length,&CaseNum);
    for(int i=0; i<=length; i++){
            road[i] = true;
        }
    int number = length+1;
    while(CaseNum--){
        int left,right;
        scanf("%d%d",&left,&right);
        for(int j=left; j<=right; j++){
            if(road[j]){
                road[j] = false;
                number--;
            }
        }
    }
    printf("%d\n",number);
    return 0;
}

编辑于 2020-02-12 11:03:38 回复(0)