自动搬运

查看原文

来自洛谷，原作者为

	wxwoo 一个沉迷文化课的OIer还有可能找回曾经热爱信息学的那个自己吗？

搬运于2025-08-24 21:25:44，当前版本为作者最后更新于2018-12-10 22:29:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$$\color{#0e90d2}\huge{\texttt{my blog}}$$

原题目链接

我们可以将

    ________
   |   __   |
   |  |  |  |
---------------->
   2  5  9  11

的重叠覆盖情况看成

    _____
   |   __|__
   |  |  |  |
---------------->
   2  5  9  11

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

例如微调样例：

3

-1 1

2 11

5 9

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

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

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

代码如下

#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;
}