最优化题解 | #相差不超过k的最多数#

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int num[200005];

int main() {
    int n,k;
    int head, tail;
    cin >> n >> k;
    for(int i=0; i<n; i++) {
        scanf("%d", num+i);
    }
    sort(num, num+n);
    for(head=0, tail=0; tail<n; tail++) { //关键的最优就在这个循环
        if(num[tail] - num[head] > k) head++;
    }
    cout << tail-head << endl;
    return 0;
}

这里我们可以知道tail-head一定是最大值，粗略证明如下：

最大值一定存在，当时tail和head一定相对应。

之后tail和head的差距将一直保持不变，因为条件(num[tail] - num[head] > k)一直被满足，所以head和tail同时加。

这里之所以不是tail-head+1，因为在循环的最后tail直接等于了n，相当于把这个1加上了。

通过这个方法，我们就省去了和最大值比较的过程，两个下标的总移动距离也有一点缩小，即变为2*n-最大差，而不是一般算法的2*n-与末尾相差k的距离。

作为算法的优化，这里应该是极限了，其他就是一些更细碎的了。