CF386B

崔化博 · 2022-04-17 10:35:02 · 题解

看题解里没有二分做法就上传了。

题目大意

给出一个序列和两个数 n 和 T，求对于每个 a_{i} 在 a_{i}-a_{i}+T 之间的数的个数的最大值。

做法

考虑二分，先排序一遍，然后二分求得第一个大于 a_{i}+T 的数，将他减一就是最后一个小于等于 a_{i} +T，然后再二分求第一个大于等于 a_{i} 的数，将他们相减再加一就是答案，最后再求一个最大值就可以了。

代码

#include <iostream> 
#include <cstdio>
#include <algorithm>
using namespace std;
long long n,a[105],t,maxn;
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    cin>>t;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i){
        //用STL就可以，减一再加一就等于没变所以可以去掉
        maxn=max(maxn,(long long)(upper_bound(a+1,a+n+1,a[i]+t)-lower_bound(a+1,a+n+1,a[i])));
    }
    cout<<maxn;
    return 0;
}

复杂度：