正題

題目鏈接：
洛谷：https://www.luogu.org/problemnew/show/P1496
vijos：https://vijos.org/p/1165

---

大意

有n艘被燒了的船，給出頭坐標和尾坐標，求被燒了的位置的總長度。

---

解題思路

先用離散化。把船的頭坐標排序后就會好計算很多。

---

代碼

#include<cstdio> #include<algorithm> using namespace std; struct fire{int x,y; }a[40001]; int n,begin,end,sum; bool cmp(fire xx,fire yy) {return xx.x<yy.x; } int main() {scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);}sort(a+1,a+1+n,cmp);//排序頭坐標begin=a[1].x;end=a[1].y;sum=end-begin;for (int i=1;i<=n;i++){if (a[i].x>=end) {//與前面的船完全沒有關聯begin=a[i].x;end=a[i].y;sum+=end-begin;}else if (a[i].y<=end) continue;//與前面的船重合else//多出了一部分{sum+=a[i].y-end;end=a[i].y;}}printf("%d",sum); }

總結

以上是生活随笔為你收集整理的P1496 vijos1165-火烧赤壁【离散化】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。