Quiz Master 题解

Coffee_zzz · 2023-01-26 17:15:48 · 题解

乱搞题。

分析

只需要看最大值和最小值，可以把选择的部分看成一条从最小值到最大值的线段，因为中间部分不影响答案所以可以全部取出。

考虑尺取法。记录当前线段每个数的因子出现了多少次，在 l+1 时去掉 l 的所有因子即可。

代码

#include <bits/stdc++.h>
using namespace std;
int a[100005],vis[100005];
signed main(){
    int t,n,m,l,r,i,cnt,ans;
    cin>>t;
    for(int temp=0;temp<t;temp++){
        memset(vis,0,sizeof vis);
        cin>>n>>m;
        for(i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
        ans=1e9,cnt=0,r=0;
        for(l=1;l<=n;l++){
            if(cnt>=m) ans=min(ans,a[r]-a[l]);
            else{
                for(r=r+1;r<=n;r++){
                    for(i=1;i*i<=a[r];i++){
                        if(a[r]%i==0){
                            if(i<=m) if(!vis[i]++) cnt++;
                            if(a[r]/i<=m&&i*i!=a[r]) if(!vis[a[r]/i]++) cnt++;
                        }
                    }
                    if(cnt>=m) {ans=min(ans,a[r]-a[l]);break;}
                }
                if(r==n+1) break;
            }
            for(i=1;i*i<=a[l];i++){
                if(a[l]%i==0){
                    if(i<=m) if(!--vis[i]) cnt--;
                    if(a[l]/i<=m&&i*i!=a[l]) if(!--vis[a[l]/i]) cnt--;
                }
            }
        }
        if(ans==1e9) cout<<"-1\n";
        else cout<<ans<<'\n';
    }
    return 0;
}