洛谷P1496 火烧赤壁 （模拟/离散化+差分）

分析可知：将起点和终点按照从小到大的顺序排序，对答案不会产生影响

所以此时我们得到一种模拟做法：

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=2e4+10;

 4 int n,a[N],b[N],ans;

 5 //模拟做法

 6 int main(){

 7     scanf("%d",&n);

 8     for(int i=1;i<=n;i++)

 9         scanf("%d%d",&a[i],&b[i]);

10     sort(a+1,a+n+1);sort(b+1,b+n+1);

11     for(int i=1;i<=n;i++){

12         ans+=b[i]-a[i];

13         if(i!=n)//不是最后一条线段

14             if(b[i]>a[i+1]) ans-=b[i]-a[i+1];//减去重复的

15     }

16     cout<<ans;

17 }

注意可能会有重复的，要减去。

当然，我们还可以离散化（虽然说没有必要）：

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=2e4+10;

 4 int n,ans,temp,cnt,a[N],b[N],x[2*N];

 5 int f[2*N];//判断是否有效

 6 //离散化

 7 int main(){

 8     scanf("%d",&n);

 9     for(int i=1;i<=n;i++){

10         scanf("%d%d",&a[i],&b[i]);

11         x[++cnt]=a[i];x[++cnt]=b[i];

12     }

13     sort(x+1,x+cnt+1);

14     cnt=unique(x+1,x+cnt+1)-x-1;

15     for(int i=1;i<=n;i++){

16         a[i]=lower_bound(x+1,x+cnt+1,a[i])-x;

17         b[i]=lower_bound(x+1,x+cnt+1,b[i])-x;

18         f[a[i]]++;f[b[i]]--;//差分小优化

19     }

20     for(int i=1;i<=cnt;i++){

21         temp+=f[i];

22         if(temp) ans+=x[i+1]-x[i];//累加答案

23     }

24     cout<<ans;

25 } 

什么是有效？比如：

有两对线段（x1,y1）(x2,y2) 如果x1>y2或x2>y1，那么（y2,x1）段或（y1,x2）段无用

因为排序后对答案没有影响，所以这种方法是正确的。

洛谷P1496 火烧赤壁 （模拟/离散化+差分）的相关教程结束。