LuoGu: CF354C Vasya and Beautiful Arrays
CF: C. Vasya and Beautiful Arrays
枚举答案，考虑如何快速判断是否合法。对于答案 $i$ ，每个数需要在 $[d i, di + k](d \in \mathbb N)$ 范围内，前缀和后可以在 $O(n \log n)$ 的时间内完成。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <cstdio>
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0';
flag && (x = ~x + 1);
}
template <class Type>
void write (Type x)
{
x < 0 && (putchar('-'), x = ~x + 1);
x > 9 && (write(x / 10), 0);
putchar('0' + x % 10);
}
const int N = 3e5 + 10, M = 2e6 + 10;
int n, m, w[N], s[M];
int main ()
{
read(n), read(m);
int l = 1e6, r = 0;
for (int i = 1; i <= n; i++)
{
read(w[i]), s[w[i]]++;
w[i] < l && (l = w[i]);
w[i] > r && (r = w[i]);
}
for (int i = 1; i < M; i++)
s[i] += s[i - 1];
if (l <= m + 1)
return write(l), 0;
for (int i = r; i; i--)
{
int cnt = 0;
for (int j = i; j <= r; j += i)
cnt += s[j + m] - s[j - 1];
if (cnt == n)
{
write(i);
break;
}
}
return 0;
}
|