问题标题: 酷町堂:4217 合并区间

0
0
已解决
周俊豪
周俊豪
高级光能
高级光能
#include<iostream>
using namespace std;
int main(){
	int n,a[1010],b[1010];
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=n;i++){
		while(b[i]>a[i+1]&&i<n){
			b[i]=b[i+1];
			a[i+1]=a[i];
			i++;
		}
		cout<<a[i]<<" "<<b[i]<<endl; 
	}
	return 0;
} 

代码如上,样例已过,自测样例也过了。。

可是模拟为什么就是过不了。。。

题目这里

周俊豪在2019-09-26 20:00:38追加了内容

改一个

#include<iostream>
using namespace std;
int main(){
	int n,a[1010],b[1010];
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=n;i++){
		while(b[i]>=a[i+1]&&i<n){
			if(b[i]>b[i+1]){
				b[i+1]=b[i];
			}
			else{
				b[i]=b[i+1];
			}
			a[i+1]=a[i];
			i++;
		}
		cout<<a[i]<<" "<<b[i]<<endl; 
	}
	return 0;
} 

 


0
已采纳
臧鸿志
臧鸿志
初级天翼
初级天翼

这是典型的贪心区间问题,贪心又忘了吗?
用结构体,按区间左端点从小到大排序。
遍历区间的时候判断区间右端点是否包含于上一个区间的左端点,取最大值。

0
我要回答