少年Q

用户名：yin19990129

访问量：25365

签　名：

这次一定不水了！

等　　级
排　　名	181
经　　验	6821
参赛次数	2
文章发表	71
年　　龄	21
在职情况	学生
学　　校	宿迁学院
专　　业	软件工程

　　自我简介：

TA的其他文章

53.最短路练习-题解(C++代码)只做最好的思路！
浏览：164

[传智杯]软件工程实习（C++描述）只做最好的思路！
浏览：380

[传智杯]程序员节发橙子（C++描述）只做最好的思路！
浏览：487

你可能喜欢

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

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

15.合并区间-题解(C++代码)只做最好的思路！

　　作者: 少年Q　　　　发表时间：2020-03-07 13:20:51 浏览：821　|　评论：0　

原题链接：合并区间

这题吧说来话长┭┮﹏┭┮，最近脖子扭了，强忍着把这题通过了，而且有好几种方法哦。首先我利用sort排序和这题的特征，暴力枚举了一下，答案是对的，但超限67%，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[100000],b[100000];
int main(){
	int n,m,l1,l2,r1,r2,k,w,h;
	k=1;
	cin>>n>>m;
	int s[100000];
	a[100000]={0};
	b[100000]={0};
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>l1>>r1;
	for(int i=1;i<=m;i++){
		cin>>b[i];
	}
	cin>>l2>>r2;
	for(int i=l1;i<=r1;i++){
		s[k++]=a[i];
	}
	for(int i=l2;i<=r2;i++){
		s[k++]=b[i];
	}
	sort(s,s+k);
	for(int i=1;i<k;i++){
	   for(int j=1;j<k;j++){
	   	if(s[i]==a[j]&&j<=r1&&j>=l1){
	   		cout<<1<<" ";
	   	}
		if(s[i]==b[j]&&j<=r2&&j>=l2){
	   		cout<<2<<" ";
	   	}
	   }
	}
	return 0;
}
```
后来我又尝试用了结构体和sort函数（附加了cmp，按特征排序）通过了！代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
struct sj{
	int x;
	int w;
}a[100000],b[100000];
bool cmp(sj a,sj b){
	return a.x<b.x;
}
int main(){
	int n,m,l1,l2,r1,r2,k,w,h;
	k=1;
	cin>>n>>m;
	sj s[100000];
	for(int i=1;i<=n;i++){
		cin>>a[i].x;
		a[i].w=1;
	}
	cin>>l1>>r1;
	for(int i=1;i<=m;i++){
		cin>>b[i].x;
		b[i].w=2;
	}
	cin>>l2>>r2;
	for(int i=l1;i<=r1;i++,k++){
		s[k].x=a[i].x;
		s[k].w=a[i].w;
	}
	for(int i=l2;i<=r2;i++,k++){
		s[k].x=b[i].x;
		s[k].w=b[i].w;
	}
	sort(s,s+k,cmp);
	for(int i=1;i<k;i++){
		cout<<s[i].w<<" ";
	}
	return 0;
}
```
后来跟着老师傅学完了归并排序，虽然归并排序（复杂度高）平常不怎么用，但其合并区间的思想在实际练习中可以套用，比如这题，简直就是为这种思想量身套用的，代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],c[100005];
int larray[100005],rarray[100005],ln,rn,lnode,rnode;
 
int main(){
	int n,m,l1,r1,l2,r2,x;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>l1>>r1;
	for(int i=1;i<=m;i++){
		cin>>b[i];
	}
	cin>>l2>>r2;
	ln=rn=0;
	for(int i=l1;i<=r1;i++){
		larray[++ln]=a[i];
	}
	for(int i=l2;i<=r2;i++){
		rarray[++rn]=b[i];
	}
	lnode=rnode=1;
	for(int i=1;i<=(r1-l1+1)+(r2-l2+1);i++){
		if(lnode>ln){
			c[i]=rarray[rnode++];
			cout<<2<<" ";
		}else if(rnode>rn){
			c[i]=larray[lnode++];
			cout<<1<<" ";
		}else if(larray[lnode]<=rarray[rnode]){
			c[i]=larray[lnode++];
			cout<<1<<" ";
		}else{
			c[i]=rarray[rnode++];
			cout<<2<<" ";
		}
	}
	return 0;
}
```

0.0分

8 人评分

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

少年Q

TA的其他文章

你可能喜欢

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

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

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

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

C语言训练-亲密数（C语言代码）

15.合并区间-题解(C++代码)只做最好的思路！

评论区

精彩推荐

【偶数求和】（C语言代码）

1048题解（读入回车问题）

Hello, world! （C语言代码）

程序员的表白（C语言代码）

复数求和（C语言代码）

C二级辅导-等差数列（C语言代码）

最好的，

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

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

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

少年Q

TA的其他文章

你可能喜欢

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

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

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

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

C语言训练-亲密数 （C语言代码）

15.合并区间-题解(C++代码)只做最好的思路！

评论区

精彩推荐

【偶数求和】 （C语言代码）

1048题解（读入回车问题）

Hello, world! （C语言代码）

程序员的表白 （C语言代码）

复数求和 （C语言代码）

C二级辅导-等差数列 （C语言代码）

最好的，

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

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

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

C语言训练-亲密数（C语言代码）

　　评论区

【偶数求和】（C语言代码）

程序员的表白（C语言代码）

复数求和（C语言代码）

C二级辅导-等差数列（C语言代码）