时间复杂度的O(n)算法

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 100010

#define maxk 100010

//0 <= Ai <= 100000

int n,k,arr[maxn];

vector<int> vec[maxk];

int dp[maxn];//dp[i]表示vec[]中最大值为i时的最大在线人数

bool vis[100010];

int main(){

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++){

        scanf("%d",&arr[i]);

    }

    sort(arr+1,arr+1+n);

    int ans=0,tmpans=0;

    if(k!=0){

        for(int i=1;i<=n;i++){

            vec[arr[i]%k].push_back(arr[i]/k+5);

        }

        for(int i=0;i<k;i++){

            memset(dp,0,sizeof(dp));

            memset(vis,0,sizeof(vis));

            tmpans=0;

            for(auto v:vec[i]){

                if(vis[v])dp[v]++;

                else{

                    vis[v]=1;

                    dp[v]=max(dp[v-2]+1,dp[v-3]+1);//这句是关键

                }

                tmpans=max(tmpans,dp[v]);

            }

            ans+=tmpans;

        }

    }

    else{

        for(int i=1;i<=n;i++){

            if(!vis[arr[i]]){

                vis[arr[i]]=1;

                ans++;

            }

        }

    }

    printf("%d",ans);

    system("pause");

    return 0;

}