题目链接

#1.0 题目大意

给出一个整数 \(n\) 和一个长度为 \(n\) 的数列 \(\{a_i\}\) 以及一个整数 \(t\)，求数列 \(\{a_i\}\) 中最多有几个元素 \(\in[x,x+t]\)，其中 \(x\in\{a_i\}.\)

#2.0 朴素做法

打眼一看数据范围很小，可以使用 \(O(n^2)\) 的朴素算法。

我们可以枚举 \(x\) 的取值，之后遍历整个序列，记录答案即可。

const int N = 100010;
const int INF = 0x3fffffff;

int n,t,a[N],cnt,ans;

int main(){
    scanf("%d",&n);
    for (int i = 1;i <= n;i ++)
      scanf("%d",&a[i]);
    scanf("%d",&t);
    for (int i = 1;i <= n;i ++){
        int r = a[i] + t;cnt = 0;
        for (int j = 1;j <= n;j ++)
          if (a[i] <= a[j] && a[j] <= r)
            cnt ++;
        ans = max(ans,cnt);
    }
    cout << ans;
    return 0;
}

#3.0 线段树优化

我们对 \(O(n^2)\) 的时间复杂度不是很满意，虽然它能过这道题。

朴素算法的时间复杂度瓶颈是 查询有多少数在区间 \([a_i,a_i+T]\) 中，不由得联想到 权值线段树，它可以将单次查询的时间复杂度由 \(O(n)\) 将至 \(O(\log n).\)

不过要注意，我们在建树的时候，权值线段树的维护范围应当为 \([1,M+T]\)，其中 \(M=\max\{a_i\}\)，这是因为查询时的区间为 \([a_i,a_i + T]\)，我们应当避免越界，防止出现未知的错误。

const int N = 100010;
const int MAX = 5000;
const int INF = 0x3fffffff;

struct Node{
    int l,r;
    int ls,rs;
    int sum;
};
Node p[N];

int cnt,n,T,root,a[N],mx,ans;

inline int Max(const int &a,const int &b){
    return a > b ? a : b;
}

inline int create(const int &l,const int &r){
    p[++ cnt].l = l,p[cnt].r = r;
    p[cnt].ls = p[cnt].rs = p[cnt].sum = 0;
    return cnt;
}

inline void insert(int k,int x){
    p[k].sum ++;
    if (p[k].l == p[k].r)
      return;
    int mid = (p[k].l + p[k].r) >> 1;
    if (x <= mid){
        if (!p[k].ls) p[k].ls = create(p[k].l,mid);
        insert(p[k].ls,x);
    }
    else{
        if (!p[k].rs) p[k].rs = create(mid + 1,p[k].r);
        insert(p[k].rs,x);
    }
}

inline int query(int k,int x,int y){
    if (x <= p[k].l && p[k].r <= y)
      return p[k].sum;
    int mid = (p[k].l + p[k].r) >> 1,res = 0;
    if (x <= mid) if (p[k].ls)
      res += query(p[k].ls,x,y);
    if (y > mid) if (p[k].rs)
      res += query(p[k].rs,x,y);
    return res;
}

int main(){
    scanf("%d",&n);
    for (int i = 1;i <= n;i ++){
        scanf("%d",&a[i]);
        mx = Max(mx,a[i]);
    }
    scanf("%d",&T);
    root = create(1,mx + T + 10);
    for (int i = 1;i <= n;i ++)
      insert(root,a[i]);
    for (int i = 1;i <= n;i ++)
      ans = Max(ans,query(root,a[i],a[i] + T));
    printf("%d",ans);
    return 0;
}

时间复杂度实际为 \(O(n\log (M+T))\)，其中 \(M=\max\{a_i\}.\)

#4.0 继续优化

但是我仍旧不满意，单次查询的时间复杂度可不可以优化至 \(O(1)\) 呢？

我们可以对每个数出现的次数进行统计，得到桶数组 b[i]，再对 b[i] 做前缀和，得到前缀和数组 sum[i]，之后，数列 \(\{a_i\}\) 在区间 \([a_i,a_i+T]\) 内出现的数的个数便是 sum[a[i] + T] - sum[a[i] - 1]，注意是 a[i] - 1，因为我们所求的数组是闭区间。

const int N = 100010;
const int INF = 0x3fffffff;

int n,a[N],b[N],sum[N],T,mx,ans;

inline int Max(const int &a,const int &b){
    return a > b ? a : b;
}

int main(){
    scanf("%d",&n);
    for (int i = 1;i <= n;i ++){
        scanf("%d",&a[i]);
        b[a[i]] ++;
        mx = Max(mx,a[i]);
    }
    scanf("%d",&T);
    for (int i = 1;i <= mx + T + 1;i ++)
      sum[i] = sum[i - 1] + b[i];
    for (int i = 1;i <= n;i ++)
      ans = Max(ans,sum[a[i] + T] - sum[a[i] - 1]);
    printf("%d",ans);
    return 0;
}

时间复杂度应为 \(O(n+M+T)\)，其中 \(M=\max\{a_i\}.\)

不过要注意，因为用到了桶，所以如果 \(a_i\) 的值可以特别大，那么这样做便不行了。

有点意思的是，用这个程序跑出的结果：

我：？？？这个用时？？？

End

希望能给您带来帮助。