【sorting+双指针+数学】CF845div2 C. Quiz Master

系统管理员 2024-03-22 15:30 5阅读 0赞

和我一开始想的不太一样

一开始想的也是排序，然后双指针，但是我想的双指针是l=1,r=n的，因为我没注意到**极差尽可能小这个条件可以转化为区间长度最短**

其实就是尺取法，然后合法性就是这个区间内的数的所有因子能填满1~m这些格子

找出最短的区间即可

题意：

![4f0689a2229d422b99b24131f6a9cb7b.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=998244353;
    
    vector<int> F[mxn];
    
    int N,M,ok=0,tot=0;
    int a[mxn],cnt[mxn];
    
    void init(){
    	for(int i=1;i<=1e5;i++){
    		for(int j=i;j<=1e5;j+=i){
    			F[j].push_back(i);
    		}
    	}
    }
    void upd(int x,int k){
    	if(x>M) return;
    	if(k==1){
    		cnt[x]++;
    		if(cnt[x]==1) tot++;
    	}else{
    		cnt[x]--;
    		if(cnt[x]==0) tot--;
    	}
    	ok=(tot==M);
    }
    void solve(){
    	tot=0,ok=0;
    	cin>>N>>M;
    	for(int i=0;i<=M;i++) cnt[i]=0;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	sort(a+1,a+1+N);
    	int r=1,ans=1e9;
    	for(int l=1;l<=N;l++){
    		while(!ok&&r<=N){
    			for(int j=0;j<F[a[r]].size();j++) upd(F[a[r]][j],1);
    			r++;
    		}
    		if(ok&&l<=r) ans=min(ans,a[r-1]-a[l]);
    		for(int j=0;j<F[a[l]].size();j++) upd(F[a[l]][j],-1);
    	}
    	if(ans==1e9) ans=-1;
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
    	init();
        while(__--)solve();return 0;
    }

[4f0689a2229d422b99b24131f6a9cb7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/f15590cc96c54b27a7d8dbea17127ae6.png