题目描述

暴雨过后，FJ的农场到镇上的公路上有一些泥泞路，他有若干块长度为L的木板可以铺在这些泥泞路上，问他至少需要多少块木板，才能把所有的泥泞路覆盖住。

输入输出格式

输入格式：

第一行为正整数n(≤10000)和L(≤10000)，分别表示有多少段泥泞路和木板的长度；接下来n行，每一行两个整数s和e(s≤e≤10^9)，表示每一段泥泞路的起点和终点。

输出格式：

仅一个正整数，表示木板数。

输入输出样例

输入样例#1：

输出样例#1：

解题思路:

一道模拟题,我们用结构体来存所有泥泞路段的左端点和右端点.先按左端点从小到大排序,从左到右处理,处理每一段泥泞路时,计算当前需多少木板,再向后处理区间重叠情况即可.

AC代码:

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int n,l,ans;

 struct kkk {

     int s,e;

     bool vis;

 }e[];

 bool cmp(kkk a,kkk b) {

     return a.s < b.s;

 }

 int main() {

 //    freopen("cover.in","r",stdin);

 //    freopen("cover.out","w",stdout);

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

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

         scanf("%d%d",&e[i].s,&e[i].e);

         e[i].vis = ;

     }

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

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

         if(e[i].s <= e[i-].e) {

             e[i-].vis = ;

             e[i].s = e[i-].s;

         }

     }

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

         if(!e[i].vis) {

             int len = e[i].e - e[i].s;

             if(len % l == ) {

                 ans += len / l;//计算当前区间需木板数

                 int u = e[i].e - ; //以下为处理重叠区间

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

                     if(u < e[j].s) break;

                     if(u >= e[j].e) {

                         e[j].vis = ;

                         continue;

                     }

                     if(u >= e[j].s) e[j].s = u + ;

                 }

         }

         else {

                 ans += (len / l) + ;

                 int u = e[i].s + (len / l + ) * l - ;

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

                     if(u < e[j].s) break;

                     if(u >= e[j].e) {

                         e[j].vis = ;

                         continue;

                     }

                     if(u >= e[j].s) e[j].s = u + ;

                 }

             }

         }

     }

     cout << ans;

     return ;

 }

巴特西

洛谷 P1589 泥泞路

题目描述

输入输出格式

输入输出样例

解题思路:

AC代码:

最新文章

热门文章