P1496 火烧赤壁 题解
难度：⭐⭐⭐
知识点：模拟
题目链接
序言：
额，这好像是一道离散化题，但我做成了模拟
1. 入手程序
模拟模拟模拟，完事~
我怎么这么喜欢模拟呢？（小声bb）
2. 编程思路
首先，可以将题目转化一个模型
用样例举例
3
-1 1
5 11
2 9
画图表示：
如果把首尾都sort一遍，会变成：
没有影响！
所以，我们得到了一个解法：分别对起点和终点数组进行排序，加上每一条线段的长度，若与前一条线段重复减去重复部分，即可算出正确答案~
3. AC代码
#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
int s[20005],e[20005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i]>>e[i];
}
sort(s+1,s+1+n);
sort(e+1,e+1+n);
for(int i=1;i<=n;i++)
{
ans+=e[i]-s[i];//加上当前长度
if(i+1<=n)//如果不是最后一条,则有可能与前一条重复
{
if(e[i]>s[i+1])//如果重复
{
ans-=e[i]-s[i+1];//去掉重复
}
}
}
cout<<ans;
return 0;
}
