s**********r
发帖数: 141 | 1 I saw there's a long discussion on the following problem (I modified the
description a bit).
"给一个整数数组a[0...n]，找出一个size k(1
distance中，使得其min distance 最大化 (max-mindist)."
It bothered me for a while (Simply I am not a DP fan). I consider it as a
binary search problem:
0. Sort the array in ascending order. O(nlogn)
1. If you claim the max-mindist is w, I can verify it in O(n).
2. Note that '0 <= w <= (a[n]-a[0])', you can try possible w's using
binary search.
3. Time comple |
P*******e
发帖数: 1353 | 2 how do you verify 1 in O(n)?
pair-
【在 s**********r 的大作中提到】
: I saw there's a long discussion on the following problem (I modified the
: description a bit).
: "给一个整数数组a[0...n]，找出一个size k(1: distance中，使得其min distance 最大化 (max-mindist)."
: It bothered me for a while (Simply I am not a DP fan). I consider it as a
: binary search problem:
: 0. Sort the array in ascending order. O(nlogn)
: 1. If you claim the max-mindist is w, I can verify it in O(n).
: 2. Note that '0 <= w <= (a[n]-a[0])', you can try possible w's using
: binary search.
|
f*****s
发帖数: 29 | 3 dynamic programming
pair-
【在 s**********r 的大作中提到】
: I saw there's a long discussion on the following problem (I modified the
: description a bit).
: "给一个整数数组a[0...n]，找出一个size k(1: distance中，使得其min distance 最大化 (max-mindist)."
: It bothered me for a while (Simply I am not a DP fan). I consider it as a
: binary search problem:
: 0. Sort the array in ascending order. O(nlogn)
: 1. If you claim the max-mindist is w, I can verify it in O(n).
: 2. Note that '0 <= w <= (a[n]-a[0])', you can try possible w's using
: binary search.
|
k*i
发帖数: 220 | 4 能详细说说吗？
【在 f*****s 的大作中提到】
: dynamic programming
:
: pair-
|
s**********r
发帖数: 141 | 5 // Verify whether the window (min-dist) 'w' is valid.
// Note: v is already sorted.
bool verify(const std::vector &v, int k, int w) {
int e = v.size();
if (e < 2 || k > e) { err(); return false; }
int i = 0, j = 1;
while (j < e) {
while(v[j] - v[i] < w) {
if (++j >= e) { break; }
}
if (j < e) { i = j; ++j; --k; }
}
return k > 1 ? false : true;
}
【在 P*******e 的大作中提到】
: how do you verify 1 in O(n)?
:
: pair-
|
m*****k
发帖数: 64 | 6 能举例吗？
pair-
a
【在 s**********r 的大作中提到】
: I saw there's a long discussion on the following problem (I modified the
: description a bit).
: "给一个整数数组a[0...n]，找出一个size k(1: distance中，使得其min distance 最大化 (max-mindist)."
: It bothered me for a while (Simply I am not a DP fan). I consider it as a
: binary search problem:
: 0. Sort the array in ascending order. O(nlogn)
: 1. If you claim the max-mindist is w, I can verify it in O(n).
: 2. Note that '0 <= w <= (a[n]-a[0])', you can try possible w's using
: binary search.
|
s**********r
发帖数: 141 | 7 Key observation:
if there's a sequence S (S[0] < S[1] < ... < S[k-1]) which has size k and
it's min-dist is w in sorted array A, then we can derive another sequence
Z (Z[0] < Z[1] < ... < Z[k-1]) with size k, and Z has min-dist w1 >= w.
Hint: Since S[0] >= A[0], if you substitute S[0] with A[0], and the
sequence S now has min-dist >= w; you can move one more step to
substitutes S[1] with A[j] s.t. A[j] >= A[0]+w and A[j-1] < A[0]+w, and
the sequence now still has min-dist >=w. Pushing this idea |
p*****u
发帖数: 310 | 8 Nice solution. Anyone know dp solution? |
p*****u
发帖数: 310 | 9 Nice solution. Anyone know dp solution? |
s**********r
发帖数: 141 | 10 http://www.mitbbs.com/article_t/JobHunting/31540541.html
【在 p*****u 的大作中提到】
: Nice solution. Anyone know dp solution?
|
