最大 k 使得 A[0]<A[k], A[1]<A[k+1], ..., A[k-1]<A[2*k-1],在对每个 k 排序之后-大小 window
Maximum k such that A[0]<A[k], A[1]<A[k+1], ..., A[k-1]<A[2*k-1], after sorting each k-sized window
我需要解决这个问题的高效算法(时间复杂度小于 O(n^2)),请帮助我:
a[i..j] is called a[i..j] < b[i..j] if a[i]<b[i], a[i+1]<b[i+1], ..., a[j]<b[j] after sorting these 2 arrays.
Given array A[1..n], (n<= 10^5, a[i]<= 1000). Find the maximum of k that A[1..k] < A[k+1..2k]
For example, n=10: 2 2 1 4 3 2 5 4 2 3
the answer is 4
很容易看出 k <= n/2。所以我们可以使用蛮力(k 从 n/2 到 1),但不能使用二进制搜索。
而且我不知道如何处理 a[i] <= 1000。也许使用地图???
使用范围更新的分域树。树中的每个索引表示 window A
中有多少个数字小于它。要使 windows 有效,B
(右边的 window)中的每个元素必须在 A
(左边的 window)中有一个伙伴).当我们将数字 x
移到 A 中时,我们将 1
添加到树中的范围 [x+1, 1000]
中。对于从 B
移动到 A
的元素,在其树索引中添加 1。对于 B
中的每个新元素,将 -1
添加到它在树中的索引中。如果索引低于零,则 window 无效。
例如,我们有:
2 2 1 4 3 2 5 4 2 3
2 2
|
Tree:
add 1 to [3, 1000]
add -1 to 2
idx 1 2 3 4 5
val 0 -1 1 1 1 (invalid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4
|
Tree:
add 1 to [3, 1000]
add 1 to 2 (remove 2 from B)
add -1 to 1
add -1 to 4
idx 1 2 3 4 5
val -1 0 2 1 2 (invalid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2
|
Tree:
add 1 to [2, 1000]
add 1 to 1 (remove 1 from B)
add -1 to 3
add -1 to 2
idx 1 2 3 4 5
val 0 0 2 2 3 (valid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4
|
Tree:
add 1 to [5, 1000]
add 1 to 4 (remove 4 from B)
add -1 to 5
add -1 to 4
idx 1 2 3 4 5
val 0 0 2 2 3 (valid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4 2 3
|
Tree:
add 1 to [4, 1000]
add 1 to 3 (remove 3 from B)
add -1 to 2
add -1 to 3
idx 1 2 3 4 5
val 0 -1 2 3 4 (invalid)
我需要解决这个问题的高效算法(时间复杂度小于 O(n^2)),请帮助我:
a[i..j] is called a[i..j] < b[i..j] if a[i]<b[i], a[i+1]<b[i+1], ..., a[j]<b[j] after sorting these 2 arrays.
Given array A[1..n], (n<= 10^5, a[i]<= 1000). Find the maximum of k that A[1..k] < A[k+1..2k]
For example, n=10: 2 2 1 4 3 2 5 4 2 3 the answer is 4
很容易看出 k <= n/2。所以我们可以使用蛮力(k 从 n/2 到 1),但不能使用二进制搜索。
而且我不知道如何处理 a[i] <= 1000。也许使用地图???
使用范围更新的分域树。树中的每个索引表示 window A
中有多少个数字小于它。要使 windows 有效,B
(右边的 window)中的每个元素必须在 A
(左边的 window)中有一个伙伴).当我们将数字 x
移到 A 中时,我们将 1
添加到树中的范围 [x+1, 1000]
中。对于从 B
移动到 A
的元素,在其树索引中添加 1。对于 B
中的每个新元素,将 -1
添加到它在树中的索引中。如果索引低于零,则 window 无效。
例如,我们有:
2 2 1 4 3 2 5 4 2 3
2 2
|
Tree:
add 1 to [3, 1000]
add -1 to 2
idx 1 2 3 4 5
val 0 -1 1 1 1 (invalid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4
|
Tree:
add 1 to [3, 1000]
add 1 to 2 (remove 2 from B)
add -1 to 1
add -1 to 4
idx 1 2 3 4 5
val -1 0 2 1 2 (invalid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2
|
Tree:
add 1 to [2, 1000]
add 1 to 1 (remove 1 from B)
add -1 to 3
add -1 to 2
idx 1 2 3 4 5
val 0 0 2 2 3 (valid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4
|
Tree:
add 1 to [5, 1000]
add 1 to 4 (remove 4 from B)
add -1 to 5
add -1 to 4
idx 1 2 3 4 5
val 0 0 2 2 3 (valid)
2 2 1 4 3 2 5 4 2 3
2 2 1 4 3 2 5 4 2 3
|
Tree:
add 1 to [4, 1000]
add 1 to 3 (remove 3 from B)
add -1 to 2
add -1 to 3
idx 1 2 3 4 5
val 0 -1 2 3 4 (invalid)