wxwoo's blog

原题目链接

蒟蒻提供一个思路:

理论上,我们可以将

1
2
3
4
5
    ________
| __ |
| | | |
---------------->
2 5 9 11

的重叠覆盖情况看成

1
2
3
4
5
    _____
| __|__
| | | |
---------------->
2 5 9 11

所以,若我们将起点和终点按照从小到大的顺序排序,对答案不会产生影响

例如微调样例:

3

-1 1

2 11

5 9

和原样例答案一样,都可以看成

1
2
3
4
5
        __________
_ | ______|__
| | | | | |
------------------------>
-1 1 2 5 9 11

所以,我们得到了一个解法:分别对起点和终点进行排序,循环加上每一条线段的长度,若与前一条线段重复减去重复部分

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin>>n;
long long a[20001],b[20001],l=0;//a数组存储起点,b数组存储终点,l表示最终长度
for(int i=0;i<n;i++)
cin>>a[i]>>b[i];//输入
sort(a,a+n);
sort(b,b+n);//由于起点终点的顺序对答案不产生影响,对a数组和b数组进行排序
for(int i=0;i<n;i++)
{
l+=b[i]-a[i];//加上当前线段长度
if(i+1<n)//如果这条线段不是最后一条线段
if(b[i]>a[i+1])//如果这条线段与前一条线段有重复
l-=b[i]-a[i+1];//减去重复部分
}
cout<<l;//输出
return 0;
}

ps:蒟蒻不会离散化只能xjb模拟qwq

 评论

载入天数...载入时分秒...


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。