P1496 火烧赤壁 题解

· · 题解

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