M******k
发帖数: 51 | 1 Given an array of "n" random integers and an integer k<=n. Find the k
numbers such that the minimum difference of all the possible pairs of k
numbers is maximized (maximum among other minimum differences for various
possible selections of k numbers).
这道题有没有什么好的思路。 | h**6
发帖数: 4160 | 2 这题都被考过无数遍了，楼主请自行考古。
这里提供一道变体题，两题会做一道，另一题也会做了。
一个数组有n个元素全是正数，把这个数组分成非空的k段，每段都连续。求最每段元素
和的最大值的最小值。 | x******3
发帖数: 245 | | m*****g
发帖数: 226 | 4 请问变体如何下手？
【在 h**6 的大作中提到】
: 这题都被考过无数遍了，楼主请自行考古。
: 这里提供一道变体题，两题会做一道，另一题也会做了。
: 一个数组有n个元素全是正数，把这个数组分成非空的k段，每段都连续。求最每段元素
: 和的最大值的最小值。
| d****n
发帖数: 233 | 5 Not quite understand the question, but I guess it should be the minimum
element in the array.
since all the subsequences are non empty.
【在 m*****g 的大作中提到】
: 请问变体如何下手？
| s********a
发帖数: 1447 | | M******k
发帖数: 51 | | h**6
发帖数: 4160 | 8 这里先给出两题的DP解法，一会还有其他解法。
首先两头的点是必须找的，中间还需要k-2个点。
令1~n闭区间内k个数的最大最小差为f(1, n, k)，假设第二个点位于i处
f(1, n, k) = max(2<=i<=n+2-k) min{f(1, i, 2), f(i, n, k-1)}
f(x, y, 2) = a[y]-a[x]
变体题出自Topcoder SRM 169 Division I Level Two
令1~n闭区间分成n段的最小最大和为f(1, n, k)，假设第一段为1~i
f(1, n, k) = min(1<=i<=n+1-k) max{f(1, i, 1), f(i+1, n, k-1)}
f(x, y, 1) = a[x]+a[x+1]+...+a[y] | s*******n
发帖数: 452 | 9 原链接
http://www.mitbbs.com/article_t/JobHunting/31544893.html
http://www.mitbbs.com/article_t1/JobHunting/31540541_0_1.html
我理解各位大侠的讨论结果是这样的，大家看看对不对：
after sorting, if we select one number, the array is
divided into 2 parts, and consider taking numbers from each part. So, 从k-1
到 k 的递推公式：
f(k,head) = max_{
for i in (head+1, end-k) {
min{dis(head,i), f(k-1,i,end)}
}
} | h**6
发帖数: 4160 | 10 除了上面的DP方法，我又想出一种方法，是二分法，当然前提是所有元素必须是整数。
所求差值不会超过最大元素与最小元素的差，不会少于1，可以在这个区间内使用二分
法。
判断数组中能否取k个最小差值为d的元素是很简单的，首先取最小元素，然后
取至少大过这个元素d的最小元素，然后再取至少大d的最小元素，...，最后看看能不
能在原数组中取出这样的k个元素。
如果能，增大d，如果不能，减小d，这样可以用二分法求出d。 | | | d****n
发帖数: 233 | 11
1
【在 s*******n 的大作中提到】
: 原链接
: http://www.mitbbs.com/article_t/JobHunting/31544893.html
: http://www.mitbbs.com/article_t1/JobHunting/31540541_0_1.html
: 我理解各位大侠的讨论结果是这样的，大家看看对不对：
: after sorting, if we select one number, the array is
: divided into 2 parts, and consider taking numbers from each part. So, 从k-1
: 到 k 的递推公式：
: f(k,head) = max_{
: for i in (head+1, end-k) {
: min{dis(head,i), f(k-1,i,end)}
| M******k
发帖数: 51 | | K******g
发帖数: 1870 | 13 为什么两头的点是必须找的呢？
【在 h**6 的大作中提到】
: 这里先给出两题的DP解法，一会还有其他解法。
: 首先两头的点是必须找的，中间还需要k-2个点。
: 令1~n闭区间内k个数的最大最小差为f(1, n, k)，假设第二个点位于i处
: f(1, n, k) = max(2<=i<=n+2-k) min{f(1, i, 2), f(i, n, k-1)}
: f(x, y, 2) = a[y]-a[x]
: 变体题出自Topcoder SRM 169 Division I Level Two
: 令1~n闭区间分成n段的最小最大和为f(1, n, k)，假设第一段为1~i
: f(1, n, k) = min(1<=i<=n+1-k) max{f(1, i, 1), f(i+1, n, k-1)}
: f(x, y, 1) = a[x]+a[x+1]+...+a[y]
| Z*****Z
发帖数: 723 | 14 他说的是排序之后
【在 K******g 的大作中提到】
: 为什么两头的点是必须找的呢？
| r****o
发帖数: 1950 | 15 我做一下这个变体题，看看对不对。
设A[i][j]为前i个元素分为j段时每段元素和的最大值的最小值，则:
A[m][n]=MIN_{i=n-1..m-1}MAX{A[i][n-1], SUM_{j=i+1..m}{a[j]}}.
【在 h**6 的大作中提到】
: 这题都被考过无数遍了，楼主请自行考古。
: 这里提供一道变体题，两题会做一道，另一题也会做了。
: 一个数组有n个元素全是正数，把这个数组分成非空的k段，每段都连续。求最每段元素
: 和的最大值的最小值。
| r****o
发帖数: 1950 | 16 这两题的DP解法是不是二维就够了？
【在 h**6 的大作中提到】
: 这里先给出两题的DP解法，一会还有其他解法。
: 首先两头的点是必须找的，中间还需要k-2个点。
: 令1~n闭区间内k个数的最大最小差为f(1, n, k)，假设第二个点位于i处
: f(1, n, k) = max(2<=i<=n+2-k) min{f(1, i, 2), f(i, n, k-1)}
: f(x, y, 2) = a[y]-a[x]
: 变体题出自Topcoder SRM 169 Division I Level Two
: 令1~n闭区间分成n段的最小最大和为f(1, n, k)，假设第一段为1~i
: f(1, n, k) = min(1<=i<=n+1-k) max{f(1, i, 1), f(i+1, n, k-1)}
: f(x, y, 1) = a[x]+a[x+1]+...+a[y]
|
|
