题目描述
难度分:$1700$
输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$,$m$之和$\leq 10^5$。
每组数据输入$n(1 \leq n \leq 10^5)$,$m(1 \leq m \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^5)$。
从$a$中选一个子序列$b$,要求$1,2,…,m$中的每个数字$x$,都能在$b$中找到$x$的倍数。输出$max(b)-min(b)$的最小值。
注:子序列不一定连续。
输入样例
3
2 4
3 7
4 2
3 7 2 9
5 7
6 4 3 5 7
输出样例
-1
0
3
算法
双指针
这个题不难,但可能今天放假心野了,被这个多测搞得WA
了好多发。先做个预处理,预处理出一个二维数组$factors$,$factors[num]$中是某些$x$,$num$是这些$x$的倍数。做这个预处理需要遍历$x \in [1,N]$(其中$N=10^5$,是题面所给的$a[i]$值域上限),然后从$num=x$开始以步长$x$自增,将$x$追加到$factors[num]$中。
接下来对数组$a$排序去重,开始进行双指针算法,初始化$l=r=0$。每次无脑将$a[r]$的因子$factors[a[r]]$加入窗口哈希表$window$,只要发现$window$中不同因子的个数为$m$,即$window.size()=m$,说明$b$序列选择$a[l…r]$这些元素就能包括$[1,m]$的所有倍数。然后一边收缩窗口左边界$l$,一边用$a[r]-a[l]$更新最小极差。
复杂度分析
时间复杂度
根据调和级数公式$\frac{n}{1}+\frac{n}{2}+…+\frac{n}{n} \rightarrow lnn$,预处理的时间复杂度为$O(NlnN)$。双指针算法的时间复杂度为$O(nlnN)$,后面这个$lnN$是因为所有因子都都会进窗口一次,出窗口一次。
空间复杂度
空间瓶颈在于预处理的$factors$数组,因为多测数组的缘故,直接把整个值域$[1,10^5]$的因子预处理出来再求解多组数据是最划算的。因此,算法的额外空间复杂度为$O(NlnN)$。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, INF = 1e9;
int T, n, m;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
vector<int> factors[N];
unordered_map<int, int, custom_hash> window;
void add(int index) {
for(int factor: factors[index]) {
if(factor <= m) {
window[factor]++;
}
}
}
void erase(int index) {
for(int factor: factors[index]) {
if(factor <= m) {
window[factor]--;
if(window[factor] == 0) window.erase(factor);
}
}
}
void init() {
for(int x = 1; x <= N - 10; x++) {
for(int num = x; num <= N - 10; num += x) {
factors[num].push_back(x);
}
}
}
int main() {
scanf("%d", &T);
if(factors[1].empty()) {
init();
}
for(int cases = 1; cases <= T; cases++) {
scanf("%d%d", &n, &m);
window.clear();
vector<int> a;
for(int i = 1; i <= n; i++) {
int ai;
scanf("%d", &ai);
a.push_back(ai);
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
n = a.size();
int ans = INF;
for(int l = 0, r = 0; r < n; r++) {
add(a[r]);
while(l <= r && m == (int)window.size()) {
ans = min(ans, a[r] - a[l]);
erase(a[l]);
l++;
}
}
if(ans == INF) ans = -1;
printf("%d\n", ans);
}
return 0;
}