小哈哈

用户名：20180390139

访问量：19724

签　名：

世界上怎么会有那么聪明的人呢？

等　　级
排　　名	216
经　　验	6366
参赛次数	9
文章发表	38
年　　龄	0
在职情况	学生
学　　校	蓝翔挖掘机技校
专　　业	网络工程

　　自我简介：

我是个傻嗨，但是我会努力像个正常人

TA的其他文章

校门外的树（C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”
浏览：305

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了
浏览：397

蓝桥杯2015年第六届真题-赢球票-题解(C++代码)-------------队列的出队入队，很简单的
浏览：342

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

校门外的树（C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”

　　作者: 小哈哈　　　　发表时间：2020-02-20 16:11:40 浏览：305　|　评论：1　

原题链接：校门外的树

对于这道题有鄙人这里陈述两种解法******
	第一种复杂，第二种简单，没学过并查集的同学可以看第二种。
	
	第一种是“并查集”，这种解法有点复杂，“并查集的思想”是把相互之间有关系的元素放在不同的集合，它的思路可以区分不同的元素，而这道题对于不同的元素可以理解为，不同的区间。题目中不是说输入M行，每行两个数据吗，这两个数据其实可以看成一个区间，接下来就运用并查集的思想，把区间相互重叠的放在一个集合，注意：比如3个区间，[10,30],[20,40],[35,50],这三个区间也是一个集合的，他们虽然没有彼此之间有联系，但是你画在纸上你就发现他们还是重叠在一条线上。另外要处理一下，如果这两个区间有联系，比如A的区间为[30,50],B的区间为[40,80],那么他们就放在同一集合，而且他们的区间都要变成[30,80]。
	###没学过并查集的同学，可以在百度上搜一下哦，不然看第一种解法是看不懂的，但是第一种解法它的空间和时间上都是很优的，比用数组标记啊要快很多
	
	第二种解法很简单，这就是数组标记，这种思路在很多题是可以用的，这是一种很重要的思想，听学长说他在面试的时候用到了
	这种思路在这道题是这样的，开一个数组d[ ],开始时所有值都是0,接下来，如果 i 这个位置在公路上，那么d[ i ]=1，然后统计一下d[i]==1的个数，就是要被砍掉的数的数量，那么剩下的就可以求了，或者统计d[i]==0的个数，就是剩下的树的棵数
	
	/*#include<iostream>
    using namespace std;
    #define N 1005
    
    struct node{
    	
    	int x;
    	int y;
    	int e;
    	
    }f[N];
    
    int L,M;
    
    int max( int a,int b ){
    	
    	return a>b ? a:b;
    } 
    
    int min( int a,int b ){
    	
    	return a>b ? b:a;
    } 
    
    void Init_(  ){
    	
    	int i,j;
    	
    	for(i=1;i<=M;i++){
    		f[i].e=i;
    	}
    	
    	return ;
    }
    
    int getf( int v ){
    	
    	if( f[v].e==v )
    	return v;
    	else{
    		
    		f[v].e=getf( f[v].e );
    		return f[v].e;
    	}
    }
    
    void merge_(  int a,int b ){
    	
    	int t1,t2;
    	t1=getf( a );
    	t2=getf( b );
    	
    	if( t1!=t2 ){
    		
    		f[t2].e=t1;
    	}
    	
    	f[t1].x=min( f[t1].x,f[t2].x );
    	f[t1].y=max( f[t1].y,f[t2].y );
    	
    	f[t2].x=min( f[t1].x,f[t2].x );
    	f[t2].y=max( f[t1].y,f[t2].y );
    	
    }
    
    
    int ok( int a,int b,int c,int d ){   //这个函数是判断两个区间是否重叠
    	
    	if( c<=b&&a<=c )
    	return 1;
    	
    	if( a<=d&&c<=a )
    	return 1;
    	
    	return 0;
    }
    
    int main( ){
    	
    	int i,j;
    	cin>>L>>M;
    	
    	for(i=1;i<=M;i++){
    		
    		cin>>f[i].x>>f[i].y;
    	}
    	
    	Init_( );
    	
    	for(i=1;i<=M;i++){
    		
    		for(j=i+1;j<=M;j++){
    			
    			if( ok( f[i].x,f[i].y,f[j].x,f[j].y ) )
    			merge_( i,j );
    		}
    	}
    	
    	long sum=0;
    	for(i=1;i<=M;i++){
    		
    		if( f[i].e==i )
    		sum+=f[i].y-f[i].x+1;
    	}
    	
    	cout<<L+1-sum<<endl;
    	
    	return 0;
    }*/
    //############################第二种解法如下
    #include<iostream>
    using namespace std;
    #define N 10005
    
    int main(){
    	int i,j,k,sum=0;
    	int L,M,x,y;
    	cin>>L>>M;
    	int d[N]={0};
    	for(i=1;i<=M;i++){
    		
    		cin>>x>>y;
    		
    		for(j=x;j<=y;j++)
    		d[j]=1;  //区间[x,y]就是公路要经过的，所以这个范围的树要被砍，所以d[i]=1
    	}
    	
    	for(i=0;i<=L;i++){
    		
    		if( d[i]!=1)
    		sum++;
    	}
    	
    	cout<<sum<<endl;
    	return 0;
    }

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

wangjinbo

没有线段树差评

2020-02-22 18:26:28

小哈哈

TA的其他文章

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

字符串的输入输出处理（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

A+B for Input-Output Practice (VI) （C语言代码）

校门外的树（C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言训练-计算1977！* （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

矩形面积交（C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

printf基础练习2 （C语言代码）

拆分位数（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

小哈哈

TA的其他文章

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

字符串的输入输出处理 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C++代码）

A+B for Input-Output Practice (VI) （C语言代码）

校门外的树 （C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-8除不尽的数 （C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言训练-计算1977！* （C语言代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

矩形面积交 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

printf基础练习2 （C语言代码）

拆分位数 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

字符串的输入输出处理（C语言代码）

校门外的树（C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”

　　评论区

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

矩形面积交（C语言代码）

拆分位数（C语言代码）