求助
查看原帖
求助
358971
朦胧_XY楼主2023/8/27 17:50

两种合并区间的方法,为何一个对,一个错?

1.AC:

#include <bits/stdc++.h>
using namespace std;
/*都一样*/
struct Node{
	ll a, b;
} rgn1[N], rgn2[N];
bool cmp(Node x, Node y){ return x.b < y.b || x.b == y.b && x.a > y.a; }
int main(){
	/*都一样*/
	sort(rgn1 + 1, rgn1 + tot + 1, cmp); rgn2[len = 1] = rgn1[1];
	for(int i = 2; i <= tot; i++) if(rgn1[i].a > rgn2[len].a){
		if(rgn1[i].b <= rgn2[len].a) rgn2[len].a = rgn1[i].a;
		else rgn2[++len] = rgn1[i];
	}
	/*都一样
	return 0;
} 

2.WA:

#include <bits/stdc++.h>
using namespace std;
/*都一样*/
struct Node{
	ll a, b;
} rgn1[N], rgn2[N];
bool cmp(Node x, Node y){
	return x.a < y.a || (x.a == y.a && x.b < y.b);
}
int main(){
	/*都一样*/
	for(int i = 1; i <= tot; i++){
		rgn2[i].b = 1ll<<60;
	}
	sort(rgn1 + 1, rgn1 + tot + 1, cmp);
	for(int i = 1; i <= tot; i++) if(rgn1[i].a > rgn1[i-1].a){
		while(len && rgn1[i].b <= rgn2[len].a) len--; len++;
		rgn2[len].a = rgn1[i].a, rgn2[len].b = min(rgn2[len].b, rgn1[i].b);
	}
	/*都一样*/
	return 0;
} 
2023/8/27 17:50
加载中...