问一下这题nlogn的复杂度不行吗?
查看原帖
问一下这题nlogn的复杂度不行吗?
784813
SakurajiamaMai楼主2023/10/11 20:02

是我代码有问题吗?

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m,k;
bool vis[N];
void solve()
{
    cin>>n>>k; res=0,num=0;
    memset(vis,false,sizeof vis);
    memset(f,0,sizeof f);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        res+=a[i]/k,a[i]%=k,f[i]=a[i];
    }
    sort(f+1,f+1+n);
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        int x=lower_bound(f+i+1,f+n+1,k-f[i])-f;
        //cout<<f[i]<<' '<<f[x]<<endl;
        if(f[i]+f[x]>=k) vis[x]=true,f[x]=-1e10,res++;
    }
    cout<<res<<endl;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
2023/10/11 20:02
加载中...