題目鏈接

https://www.luogu.org/problemnew/show/P1589

解題思路

用結構體存下每一段泥濘路的左端點和右端點，然后用sort根據左端點排序，采用貪心的思想，從左往右遇到未覆蓋的點ans++，然后去覆蓋l的長度，這時現在覆蓋到的位置就是max(下一段區間的左端點，當前覆蓋到的位置)。注意每一個泥濘路段是一個區間，例如【2，5】實際上就是三個單位長度，它具有四個端點，我們記錄的是單位長度，所以while里面的是<而不是<=。

AC代碼

1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int n,l,ans; 5 struct ee{ 6 int e,s; 7 }a[10005]; 8 bool cmp(ee a,ee b){ 9 return a.s<b.s; 10 } 11 int main(){ 12 cin>>n>>l; 13 for(int i=1;i<=n;i++) cin>>a[i].s>>a[i].e; 14 sort(a+1,a+n+1,cmp); 15 int d=a[1].s; 16 for(int i=1;i<=n;i++){ 17 while(d<a[i].e){ 18 d+=l; 19 ans++; 20 } 21 d=max(d,a[i+1].s); 22 } 23 cout<<ans; 24 return 0; 25 }

?

轉載于:https://www.cnblogs.com/yinyuqin/p/10987508.html

總結

以上是生活随笔為你收集整理的洛谷 P1589 泥泞路 2019青岛市竞赛（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

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