洛谷 P1589 泥泞路 & 2019青岛市竞赛（贪心）

题目链接

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

解题思路

用结构体存下每一段泥泞路的左端点和右端点，然后用sort根据左端点排序，采用贪心的思想，从左往右遇到未覆盖的点ans++，然后去覆盖l的长度，这时现在覆盖到的位置就是max(下一段区间的左端点，当前覆盖到的位置)。注意每一个泥泞路段是一个区间，例如【2，5】实际上就是三个单位长度，它具有四个端点，我们记录的是单位长度，所以while里面的是<而不是<=。

AC代码

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int n,l,ans;

 struct ee{

     int e,s;

 }a[];

 bool cmp(ee a,ee b){

     return a.s<b.s;

 }

 int main(){

     cin>>n>>l;

     for(int i=;i<=n;i++) cin>>a[i].s>>a[i].e;

     sort(a+,a+n+,cmp);

     int d=a[].s;

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

         while(d<a[i].e){

             d+=l;

             ans++;

         }

         d=max(d,a[i+].s);

     }

     cout<<ans;

     return ;

 }

巴特西

洛谷 P1589 泥泞路 & 2019青岛市竞赛（贪心）

题目链接

解题思路

AC代码

最新文章

热门文章