蒟蒻码力太弱了,求助代码问题
查看原帖
蒟蒻码力太弱了,求助代码问题
538427
czy0323楼主2023/7/8 20:52

为什么这个代码会输出负数(除了-1以外的)?明明sort了

cf评测记录

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, m;
int a[N], vis[N];
vector<int> divi[N];

signed main(){
	int T;
	cin >> T;
	while( T-- ){
		for(int i = 1; i <= m; i++)
			vis[i] = 0;
		cin >> n >> m;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			if( divi[a[i]].size() )
				continue;
			for(int j = 1; j * j <= a[i]; j++)
				if( a[i] % j == 0 ){
					divi[a[i]].push_back(j);
					if( j * j != a[i] )
						divi[a[i]].push_back(a[i] / j);
				}
		}
		bool flag = 0;
		for(int i = 1; i <= n; i++)
			for(auto j : divi[a[i]])
				if( j <= m )
					vis[j]++;
		for(int i = 1; i <= m; i++){
			if( !vis[i] ){
				cout << -1 << "\n";
				flag = 1; vis[i] = 0;
				break;
			}
			vis[i] = 0;
		}
		if( flag )	continue;
		sort(a + 1, a + 1 + n);
		int l = 1, r = 1, fit = 0, ans = 1e9;
		while( r <= n ){
			while( fit < m ){
				if(	divi[a[r]].size() == 0 )
					break;
				for(auto i : divi[a[r]]){
					if( i > m )
						continue;
					if( !vis[i] )
						fit++;
					vis[i]++;
				}
				r++;
			}
			while( fit == m ){
				for(auto i : divi[a[l]]){
					if( i > m )
						continue;
					vis[i]--;
					if( !vis[i] )
						fit--;
				}
				l++;
			}
			ans = min(ans, a[r - 1] - a[l - 1]);
		}
		cout << ans << "\n";
	}
	return 0;
}
2023/7/8 20:52
加载中...