P2082 求助:测试用例#1 WA,其余AC
查看原帖
P2082 求助:测试用例#1 WA,其余AC
1391256
LTTXiaochuan楼主2024/7/17 21:49

基本思路:合并有交集的区间,然后将原区间归零,再统计非零区间长度(=r-l+1)。 然后以为#1含有[0,0]导致被坑,于是将清零的区间改为[-114,514]依然错误。说明不是此原因。 代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node{
	ll l;
	ll r;
};
node a[N];
bool cmp(node a,node b)
{
	return a.l<b.l;
}
int main()
{
	int n;
	cin>>n;
	ll x,y,le=0;
	for(int i=1; i<=n; i++)
	{
		scanf("%lld %lld",&x,&y);
		a[i].l=x;
		a[i].r=y;
	}
	sort(a+1,a+n,cmp);
	for(int i=1; i<=n-1; i++)
	{
		if(a[i+1].l<=a[i].r && a[i+1].r>=a[i].r)
		{
			a[i+1].l=a[i].l;
			a[i].l=0;
			a[i].r=0;
		}
		else if(a[i+1].l<=a[i].r)
		{
			a[i+1].l=a[i].l;
			a[i+1].r=a[i].r;
			a[i].l=0;
			a[i].r=0;
		}
	}
	for(int i=1; i<=n; i++)
	{
		if(a[i].l!=0 && a[i].r!=0)
			le+=a[i].r-a[i].l+1;
	}
	cout<<le;
	return 0;
}
2024/7/17 21:49
加载中...