AcWing 1162. 阴谋
原题链接
简单
作者:
cocoonnnp
,
2022-04-01 22:23:29
,
所有人可见
,
阅读 173
排序 遍历 判断
//做题还是要严谨啊!!! 不能随便去提交啊!!先检查代码 判断一般情况!!!
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=10010;
struct line{
LL l,r;
bool operator <(const struct line &x){
return l<x.l;
}
}a[N],b[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) scanf("%lld %lld",&a[i].l,&a[i].r);
sort(a,a+n);
int t=0;
b[0].l=a[0].l;
b[0].r=a[0].r;
for(int i=1;i<n;i++)
{
//cout<<a[i].l<<" "<<a[i].r<<endl;
if(a[i].l<=b[t].r)
{
if(a[i].r>b[t].r) b[t].r=a[i].r;
}else
{
t++;
b[t].l=a[i].l;
b[t].r=a[i].r;
}
}
LL ans=0;
for(int i=0;i<=t;i++)
{
//cout<<b[i].l<<" "<<b[i].r<<endl;
ans+=b[i].r-b[i].l;
}
printf("%lld",ans);
return 0;
}