题目:Defeat the monster
来源:哈尔滨理工大学软件与微电子学院程序设计竞赛(同步赛)
解题思路
从 N 个数中挑选一些数,挑选的数中任意两个数相差不超过 5,求最多能挑选多少个数?
双指针、滑动窗口:
先对 N 个数进行排序,然后使用 i
和 j
分别指向前后两个数。
如果 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; }