题解 P1296 【奶牛的耳语】

autoencoder · 2018-07-27 14:09:46 · 题解

这道题主要思路在于始终维持一个大小为d的滑动窗口，统计窗口中的奶牛对数。

代码复杂度：O(nlogn)+O(n)=O(nlogn)

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

int p[1000001];

int main() {
    int n, d, count = 0;
    cin >> n >> d;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    sort(p, p+n);
    /*
    这里我们手动添加一个奶牛，把这个奶牛所在的
    位置设置为任何一个奶牛都不可能到达的位置。
    这样的好处在于在后面循环的时候不需要单独考
    虑当i>=n时j<i-1的特殊情况。为什么会有特殊
    情况呢？

    思路就是i不断向右寻找窗口的右边界，j表示窗
    口左边界。一旦发现i所指向的奶牛和j所指向的
    奶牛距离超过了d就表示窗口已经大于d了（我们
    始终希望窗口的大小是小于等于d的），这时候
    i-1就是最后一个可以跟j聊天的奶牛，这时候
    在窗口中的奶牛对数为(i-1-j)。
    */
    p[n] = p[n-1] + d + 1;
    int i = 0, j = 0;
    while (i <= n) {
        if (p[i] - p[j] > d) {
            count += i - j - 1;
            j++;
        } else {
            i++;
        }
    }

    cout << count << endl;
}

有特殊情况的代码：

    int i = 0, j = 0;
    while (i < n) {
        if (p[i] - p[j] > d) {
            count += i - j - 1;
            j++;
        } else {
            i++;
        }
    }
    // 特殊情况处理，也可使用求和公式
    while (j < i) {
        count += i - j - 1;
        j++;
    }

特殊情况发生在如果i不断递增超过了n-1，也就是循环结束但事实上j依然距离i有一段距离，也就是说当循环结束时，由j和i表示的窗口中的所有的奶牛依然可以互相联络，这时候我们就需要特殊处理。通过这个例子我们就可以看出手动增加一个奶牛的好处了。