题目简述
给定一个长度为 \(n\) 的正整数序列 \(a\),以及一个正整数 \(m\)。在序列 \(a\) 中选出一个长度为子序列(不是子段) \(b\) ,\(\forall i \in [1, m] ,\exists b_j, b_j\) 能整除 \(i\)。
求所有满足条件的序列 \(b\) 的极差(最大值于最小值的差)的最小值;若无满足条件序列 \(b\) ,输出 \(-1\) 。
思路
考虑先排序。
将序列排序之后,如果区间 \(a[l, r]\) 满足条件,则 \(a[l, r + 1]\) 一定不优;如果区间 \(a[l, r]\) 不满足条件,则 \(a[l + 1, r]\) 一定不满足条件。
所以可以考虑双指针,每次将右端点向右移一位。考虑删去左端点,若可以整除的数没有减少,则删去左端点。
代码
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
const int N = 1E5 + 5;
int t, n, m;
int a[N];
int b[N];
int main()
{
cin >> t;
while (t--) {
memset(b, 0, sizeof(b));
cin >> n >> m;
for (int i = 1; i <= n ;i++) cin >> a[i];
sort (a + 1, a + n + 1);
int l = 1, ans = 0x3F3F3F3F, now = 0;
for (int r = 1; r <= n; r++) {
for (int i = 1; i * i <= a[r]; i++) {
if (a[r] % i == 0) {
if (!b[i] && i <= m) now++;
if (i * i != a[r] && !b[a[r] / i] && a[r] / i <= m) now++;
b[i]++;
if (i * i != a[r]) b[a[r] / i]++;
}
}
while (l < r) {
bool ok = 1;
for (int i = 1; i * i <= a[l]; i++) {
if (a[l] % i == 0) {
if (b[i] == 1 && i <= m || b[a[l] / i] == 1 && a[l] / i <= m ) {
ok = 0;
break;
}
}
}
if (!ok) break;
for (int i = 1; i * i <= a[l]; i++) {
if (a[l] % i == 0) {
b[i]--;
if (i * i != a[l]) b[a[l] / i]--;
}
}
l++;
}
if (now == m) ans = min(a[r] - a[l], ans);
}
if (ans == 0x3F3F3F3F) cout << -1;
else cout << ans;
cout << '\n';
}
}
标签:满足条件,CF1777C,int,题解,Master,端点,序列
From: https://www.cnblogs.com/easonhe/p/17397424.html