题目:Defeat the monster
来源:哈尔滨理工大学软件与微电子学院程序设计竞赛(同步赛)

解题思路

从 N 个数中挑选一些数,挑选的数中任意两个数相差不超过 5,求最多能挑选多少个数?

双指针、滑动窗口:
先对 N 个数进行排序,然后使用 ij 分别指向前后两个数。
如果 w[j] - w[i],记录满足条件的 j-i+1 的最大值,右移 j;否则,右移 i

C++代码

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

int main(){
    int N;
    cin >> N;
    vector<int> w(N);
    for(int i=0; i<N; ++i)
        cin >> w[i];
    sort(w.begin(), w.end());
    int i=0;
    int j=1;
    int ans = 1;
    while(j < N){
        if(w[j]-w[i] <= 5){
            ans = max(ans, j-i+1);
            ++j;
        }
        else
            ++i;
    }
    cout << ans << endl;
    return 0;
}