Farmer John has a problem: the dirt road from his farm to town has suffered in the recent rainstorms and now contains (1 <= N <= 10,000) mud pools.

Farmer John has a collection of wooden planks of length L that he can use to bridge these mud pools. He can overlap planks and the ends do not need to be anchored on the ground. However, he must cover each pool completely.

Given the mud pools, help FJ figure out the minimum number of planks he needs in order to completely cover all the mud pools.
Input

  • Line 1: Two space-separated integers: N and L

  • Lines 2…N+1: Line i+1 contains two space-separated integers: s_i and e_i (0 <= s_i < e_i <= 1,000,000,000) that specify the start and end points of a mud pool along the road. The mud pools will not overlap. These numbers specify points, so a mud pool from 35 to 39 can be covered by a single board of length 4. Mud pools at (3,6) and (6,9) are not considered to overlap.
    Output

  • Line 1: The miminum number of planks FJ needs to use.
    Sample Input

    3 3
  1 6
  13 17
  8 12

Sample Output

5

如果使用暴力解决，会超时：

#include<iostream>
#include<cstdio>
int a[10010]={};
using namespace std;
int main()
{
    int N,L,m,n,x=0,min=10100,max=0,s=0;
    cin>>N>>L;
    while(N--)
    {
        cin>>m>>n;
        for(int i=m;i<=n;i++)
        a[i]=1;
        if(m<min)
            min=m;
        if(n>max)
            max=n;
    }
    x=(max-min)/L;
    for(int i=min;i<=max;i++)
    {
       if(a[i]==0)
       {
           s++;
           if(s==L)
           {
               x--;
           }
       }
       else s=0;
    }
    cout<<x<<endl;
    return 0;
}

这是之前的暴力做法，即遍历查询判断，显然部分优化也无济于事（仍然会超时）

非暴力手段：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define PI acos(-1.0)
#define N 100001
#define MOD 123
#define E 1e-6
using namespace std;
int a[N];
int main()
{
    int n,l;
    scanf("%d%d",&n,&l);
    n*=2;
    for(int i=1;i<=n;i+=2)
        scanf("%d%d",&a[i],&a[i+1]);
    sort(a+1,a+n+1);
     for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    int k=0;
    int cnt=0;
    for(int i=1;i<=n;i+=2)
    {
        if(k>=a[i+1])              //表示该段泥潭全覆盖
            continue;
        if(k>a[i])                   重新定义泥塘起始端（前面的已被木板覆盖）
            a[i]=k;
        int num=(a[i+1]-a[i])/l;        
        if( (a[i+1]-a[i])%l )          //用以判断是否需要部分木板来挡住泥塘
            num++;
        cnt+=num;
        k=num*l+a[i];            //k为木板覆盖长度
    }
    printf("%d\n",cnt);
    return 0;
}