高速公路维修问题

落日映苍穹つ 2023-02-23 05:26 4阅读 0赞

最近十几年，我们国家的高速公路发展迅速，覆盖全国的高速公路里程数逐年增加，由于建设速度快，也带来了一个问题，那就是高速公路的建设质量令人担心，但并不是所有的问题都是由建设质量一方面造成的，长期的超载超限运营也会造成路基路面的损坏，我们常常看到有些路段的路面坑坑洼洼的，一旦路面出现问题，很有可能造成严重的交通事故，因此需要修复，高速公路的修复有很多特殊性，比如一个小的坑洼，不是补一补就可以的，需要在坑洼的附近一段里面都挖掉重新铺设材料，哪怕是只有一个小的坑洼也一样，甚至一个小洼地的修补和很多个连在一起的洼地修复的成本是一样的。现在我们把一个最小的修复长度算作一个修补单位，在这个长度范围内一个洼地和多个洼地的修补成本是一样的，现在给你在一条高速公路上所有的洼地的位置（我们假定起点为高速公路的一端，另一端足够长），请你帮忙写个程序计算一下，如要修复所有的洼地，最少需要多少个修补单位。

Input

本问题有多组测试数据，每一组数据有两行，第一行有两个整数N和L（中间用空格分隔），分别表示N（0<=N<=1000）个洼地和修补单位的长度L（0<L<=100）。第二行共有N个整数a1,a2…an（用空格分隔），分别表示N个洼地的位置（0<=ai<=20000）。

Output

对于每组输入只有一行输出，即最少需要的修补单位个数。

Sample Input

2 50
    10 61
    4 50
    10 59 60 61

Sample Output

2
    2

代码

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int a[20010];
    int main()
    {
        
    
        int n,l;
        while(cin>>n>>l)
        {
        
            for(int i=0;i<n;i++)
                cin>>a[i];
            sort(a,a+n);
            int ans=0,now=-1;
            for(int i=0;i<n;i++)
            {
        
                if(a[i]<=now)continue;
                now=a[i];
                now+=l;
                ans++;
            }
            cout<<ans<<endl;
        }
        return 0;
    }