题目: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;
}
京公网安备 11010502036488号