11.04算法学习打卡

约 173 个字 30 行代码 预计阅读时间 1 分钟

打卡第14天 双指针比暴筛快了不止一点（

拿暴力筛法的时间复杂度（最坏情况为 \(\mathcal{O}(n^2)\)
比双指针慢了不止一点……

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define LL long long
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    LL n,k;
    while(T--){
    LL cnt1=0;
    LL cnt2=0;
    cin>>n>>k;
    vector<LL>a(n);
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a.begin(),a.end());
    for(int i=0,j=0;i<n;i++){
        while(j<n&&a[j]-a[i]<=k)
            j++,cnt2++;
        cnt1=max(cnt1,cnt2);
        cnt2--;
    }    
    cout<<cnt1<<endl;
    }
    return 0;
}

距离2025年结束还有58天……

从未感叹时间流逝如此之快，
开学以来每天都是碌碌无为
有的同学已经开始准备回家过年了）
看看这些天能不能再学点东西吧

TMD体测终于结束了，不知道能不能及格

评论