題目連結:http://codeforces.com/contest/1133/problem/C
題意是給了n個數,讓你找出m個數,使得這m個數中的最大值減去最小值不大于5,求最大的m
本來感覺暴力可以寫,但是不知道為什麼wa8(可能姿勢不太對,看别人的O(n)掃一遍也能過),然後就用upper_buond寫了,先排個序,然後對于每一位去求第一個大于pre[i]+5所在的位置,進而更新最大值就好了。
AC代碼:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int pre[200005];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&pre[i]);
}
sort(pre, pre + n);
int ans = 1;
for(int i=0;i<n-1;i++){
int cnt = upper_bound(pre, pre + n, pre[i] + 5) - pre;
ans = max(ans, cnt - i);
}
cout<<ans<<endl;
return 0;
}
複制