框体排列

单点限制：1.0sec
内存限制：512MB

数轴上有 n 个点，每个点有一个坐标 ai。现在需要用数个宽度为 k 的框体覆盖数轴上全部 n 个点，求出最少需要的框体数量。

输入格式

第一行两个整数 n,k(1≤n≤105,1≤k≤109)，分别代表点的数量和框体宽度。

第二行 n 个整数，第 i 个整数 ai(1≤ai≤109) 代表第 i 个点在数轴上的坐标。

输出格式

一行一个整数，代表需要的最少框体数量。

样例1

输入：
4 1
1 2 3 4
输出:
2
解释：可以将两个框体分别放在[1,2]和[3,4]两个位置

样例2

输入：
4 3
1 2 3 4
输出：
1
解释：只需要将一个框体放在[1,4]

思路分析

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

int binarySearchFirstMaxNumber(const int x[], int n, int ans) {
    int l = 0;
    int r = n - 1;
    int index = -1;
    while (l <= r) {
        int mid = (r - l) / 2 + l;
        if (x[mid] > ans) {
            index = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return index;
}

int getMinimumQuantityK(const int x[], int n, int k) {
    int count = 1;
    int i = 0;
    int ans = x[i] + k;
    while (i < n) {
        if (ans >= x[n - 1]) {
            break;
        }
        // find next
        i = binarySearchFirstMaxNumber(x, n, ans);
        ans = x[i] + k;
        count++;
    }
    return count;
}

int main() {
    int n, k;
    cin >> n >> k;
    int x[n];
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    sort(x, x + n);
    cout << getMinimumQuantityK(x, n, k);
    return 0;
}

提交结果