一条公路上有N个村落。村落i的位置是Xi。

Question

 

Answer 1

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, r;
int a[1005];
void solve()
{
    sort(a, a + n);
    int i = 0, ans = 0;
    while (i < n)
    {
        int s = a[i++];//s是没有被覆盖的最左边的点的位置
        while (i < n && a[i] <= s + r)//一直往右前进直到距s的距离大于r的点
            i++;
        int p = a[i - 1];//p是新加上标记的点的位置
        while (i < n && a[i] <= p + r)//一直往右前进直到距p的距离大于r的点
            i++;
        ans++;
    }
    cout << ans << endl;
}
int main()
{
    cin >> n;
    cin >> r;
    for (int i = 0;i < n;i++)
       cin >> a[i];
    solve();
    return 0;
}