A*********r
发帖数: 564 | 1 受到大虾的指点，本题除了DP算法，还有非DP的简单算法, 我的理解如下：
思路就是利用给定的数组范围确定pair distance的最大值和最小值，在这个范围里寻找一个最大的半径X，使得这个半径有K个元素两两距离不小于X；但所有比这个半径大的数，都只有少于K个元素的子集。
这个的算法复杂度是O(MN), 如果还要继续优化的话，就是在查找X的时候用上binary search, 把算法复杂度降为O(MlogN）。(当然前提也是要sort数组先O(M*logM)或者O(M)）。
min=0;
max=N;
while(min
{
x=(min+max)/2;
count=1;
prev=a[0];
for(i=1;i
{
if(a[i]-prev>=x)
count++；
if(count>=k) break;
}
if(count
else min=x;
}
================================== |
t****a
发帖数: 1212 | 2 Well it is pretty good idea for the binary search here.
DP.
【在 A*********r 的大作中提到】
: 受到大虾的指点，本题除了DP算法，还有非DP的简单算法, 我的理解如下：
: 思路就是利用给定的数组范围确定pair distance的最大值和最小值，在这个范围里寻找一个最大的半径X，使得这个半径有K个元素两两距离不小于X；但所有比这个半径大的数，都只有少于K个元素的子集。
: 这个的算法复杂度是O(MN), 如果还要继续优化的话，就是在查找X的时候用上binary search, 把算法复杂度降为O(MlogN）。(当然前提也是要sort数组先O(M*logM)或者O(M)）。
: min=0;
: max=N;
: while(min: {
: x=(min+max)/2;
: count=1;
: prev=a[0];
|
h**k
发帖数: 3368 | 3 赞一个。最后使用的二分查找实在是太巧妙了。
另外，N是为了直接用二分查找来做这题的。
DP.
【在 A*********r 的大作中提到】
: 受到大虾的指点，本题除了DP算法，还有非DP的简单算法, 我的理解如下：
: 思路就是利用给定的数组范围确定pair distance的最大值和最小值，在这个范围里寻找一个最大的半径X，使得这个半径有K个元素两两距离不小于X；但所有比这个半径大的数，都只有少于K个元素的子集。
: 这个的算法复杂度是O(MN), 如果还要继续优化的话，就是在查找X的时候用上binary search, 把算法复杂度降为O(MlogN）。(当然前提也是要sort数组先O(M*logM)或者O(M)）。
: min=0;
: max=N;
: while(min: {
: x=(min+max)/2;
: count=1;
: prev=a[0];
|
t*******7
发帖数: 108 | |
A*********r
发帖数: 564 | 5 你的意思是直接用2分查找作，而不用DP？
能简单说一下思路吗？
【在 h**k 的大作中提到】
: 赞一个。最后使用的二分查找实在是太巧妙了。
: 另外，N是为了直接用二分查找来做这题的。
:
: DP.
|
t****a
发帖数: 1212 | 6 han6 post his solution on the previous discussion
【在 A*********r 的大作中提到】
: 你的意思是直接用2分查找作，而不用DP？
: 能简单说一下思路吗？
|
h**k
发帖数: 3368 | 7 版上有人说过的。因为值域是1-N，所以solution的可能范围是0-N/k。对一个给定的值
x，我们很容易判断是否能找到k个元素，使得他们之间的最小距离大于等于x，这个判
断需要O(M)。注意，如果对于x不能找到这么k个元素，那么对于任何x'>x，都不可能找
到。这就构成了二分查找的判定条件，可以用二分查找找到最大的整数x，使得对于x我
们能发现k个元素。总的时间是O(MlogN)。
【在 A*********r 的大作中提到】
: 你的意思是直接用2分查找作，而不用DP？
: 能简单说一下思路吗？
|
A*********r
发帖数: 564 | 8 谢谢，一门心思看dp, 忽略了他的帖子。。
【在 t****a 的大作中提到】
: han6 post his solution on the previous discussion
|
A*********r
发帖数: 564 | 9 嗯，谢谢，这个比DP好理解多了，除非出题人故意刁难说N很大，否则这个时间复杂度
肯定比DP好啊。。
【在 h**k 的大作中提到】
: 版上有人说过的。因为值域是1-N，所以solution的可能范围是0-N/k。对一个给定的值
: x，我们很容易判断是否能找到k个元素，使得他们之间的最小距离大于等于x，这个判
: 断需要O(M)。注意，如果对于x不能找到这么k个元素，那么对于任何x'>x，都不可能找
: 到。这就构成了二分查找的判定条件，可以用二分查找找到最大的整数x，使得对于x我
: 们能发现k个元素。总的时间是O(MlogN)。
|
A*********r
发帖数: 564 | 10 有一点想不通，如何只用O(M)判断是否能找到K个元素，使得他们之间的最小距离大于
等于给定的X？
【在 h**k 的大作中提到】
: 版上有人说过的。因为值域是1-N，所以solution的可能范围是0-N/k。对一个给定的值
: x，我们很容易判断是否能找到k个元素，使得他们之间的最小距离大于等于x，这个判
: 断需要O(M)。注意，如果对于x不能找到这么k个元素，那么对于任何x'>x，都不可能找
: 到。这就构成了二分查找的判定条件，可以用二分查找找到最大的整数x，使得对于x我
: 们能发现k个元素。总的时间是O(MlogN)。
|
|
|
h**k
发帖数: 3368 | 11 greedy算法。
【在 A*********r 的大作中提到】
: 有一点想不通，如何只用O(M)判断是否能找到K个元素，使得他们之间的最小距离大于
: 等于给定的X？
|
A*********r
发帖数: 564 | 12 (根据建议，修改非DP版本如下）
min=0;
max=N;
while(min
{
x=(min+max)/2;
count=1;
prev=a[0];
for(i=1;i
{
if(a[i]-prev>=x)
count++；
if(count>=k) break;
}
if(count
else min=x;
}
【在 h**k 的大作中提到】
: greedy算法。
|
h**6
发帖数: 4160 | 13 楼上的代码好像仍然不是很对，这是两个版本的代码，假设a已排序。
由于a排序需要额外的复杂度，因此两个版本的复杂度差别不是很大。
逐个查找，O(M)，总复杂度O(MlogM+MlogN)
bool findelements(int* a, int M, int K, int x)
{
int prev = a[0];
int count = 1;
for(int i=1; i
{
if(a[i] >= prev+x)
{
count++;
prev = a[i];
}
}
return count>=K;
}
二分查找，O(KlogM)，总复杂度O(MlogM+KlogMlogN)
bool findelements(int* a, int M, int K, int x)
{
int* prev = a;
for(int i=1; i
{
int* curr = lower |
h**k
发帖数: 3368 | 14 你这个程序是直接用二分法找到最大的x么？
如果是的话，中间for循环里找k个元素满足最小距离大于x的代码，好像不对。
应该是
int count = 1;
int pre_ele = a[0];
for( int i=1; i
{
if( a[i] - pre_ele >= x )
{
count++;
pre_ele = a[i];
}
}
【在 A*********r 的大作中提到】
: (根据建议，修改非DP版本如下）
: min=0;
: max=N;
: while(min: {
: x=(min+max)/2;
: count=1;
: prev=a[0];
: for(i=1;i: {
|
s*****v
发帖数: 360 | 15 不赞不行
寻找一个最大的半径X，使得这个半径至少有K-1个pair distance；但所有比这个半径
大的数，都只有少于K-1个pair distance。
search, 把算法复杂度降为O(MlogN）。(当然前提也是要sort数组先）。
【在 A*********r 的大作中提到】
: 受到大虾的指点，本题除了DP算法，还有非DP的简单算法, 我的理解如下：
: 思路就是利用给定的数组范围确定pair distance的最大值和最小值，在这个范围里寻找一个最大的半径X，使得这个半径有K个元素两两距离不小于X；但所有比这个半径大的数，都只有少于K个元素的子集。
: 这个的算法复杂度是O(MN), 如果还要继续优化的话，就是在查找X的时候用上binary search, 把算法复杂度降为O(MlogN）。(当然前提也是要sort数组先O(M*logM)或者O(M)）。
: min=0;
: max=N;
: while(min: {
: x=(min+max)/2;
: count=1;
: prev=a[0];
|
A*********r
发帖数: 564 | 16 嗯，好像就是这个count的问题，我以为我的会收敛的更快，容我再想想。。
【在 h**k 的大作中提到】
: 你这个程序是直接用二分法找到最大的x么？
: 如果是的话，中间for循环里找k个元素满足最小距离大于x的代码，好像不对。
: 应该是
: int count = 1;
: int pre_ele = a[0];
: for( int i=1; i: {
: if( a[i] - pre_ele >= x )
: {
: count++;
|
A*********r
发帖数: 564 | 17 我们两个的2分，找的好像不是同一个东西。。
我的2分， 是为了找出在给定的1..N之中，找出一个最大的X, 使得X有k个元素的子集，所以会是O(M*LogN)。。你的2分，是在M个元素中二分，找出一个最小的合适元素curr，使得最后K元素子集的半径为X,所以复杂度是O(K*logM).
从你得到的总复杂度来看，你还是对X的范围进行了二分的，所以才会有LogN.
你最后得到的复杂度，其实是已经在两次二分的基础上得到的（对0..M一次，对0..N一次）， 所以总复杂度等于sort的复杂度+O(k*logM*logN).
我自己都快绕晕了。。
【在 h**6 的大作中提到】
: 楼上的代码好像仍然不是很对，这是两个版本的代码，假设a已排序。
: 由于a排序需要额外的复杂度，因此两个版本的复杂度差别不是很大。
: 逐个查找，O(M)，总复杂度O(MlogM+MlogN)
: bool findelements(int* a, int M, int K, int x)
: {
: int prev = a[0];
: int count = 1;
: for(int i=1; i: {
: if(a[i] >= prev+x)
|
A*********r
发帖数: 564 | 18 自己顶一下，希望han6出来确认一下，呵呵。。
集，所以会是O(M*LogN)。。你的2分，是在M个元素中二分，找出一个最小的合适元素
curr，使得最后K元素子集的半径为X,所以复杂度是O(K*logM).
一次）， 所以总复杂度等于sort的复杂度+O(k*logM*logN).
【在 A*********r 的大作中提到】
: 我们两个的2分，找的好像不是同一个东西。。
: 我的2分， 是为了找出在给定的1..N之中，找出一个最大的X, 使得X有k个元素的子集，所以会是O(M*LogN)。。你的2分，是在M个元素中二分，找出一个最小的合适元素curr，使得最后K元素子集的半径为X,所以复杂度是O(K*logM).
: 从你得到的总复杂度来看，你还是对X的范围进行了二分的，所以才会有LogN.
: 你最后得到的复杂度，其实是已经在两次二分的基础上得到的（对0..M一次，对0..N一次）， 所以总复杂度等于sort的复杂度+O(k*logM*logN).
: 我自己都快绕晕了。。
|
h**k
发帖数: 3368 | 19 han6就是实现的你改进的DP算法的最后的那个二分查找。他是想说明这里用线性查找和
二分查找效率差不多。
集，所以会是O(M*LogN)。。你的2分，是在M个元素中二分，找出一个最小的合适元素
curr，使得最后K元素子集的半径为X,所以复杂度是O(K*logM).
一次）， 所以总复杂度等于sort的复杂度+O(k*logM*logN).
【在 A*********r 的大作中提到】
: 我们两个的2分，找的好像不是同一个东西。。
: 我的2分， 是为了找出在给定的1..N之中，找出一个最大的X, 使得X有k个元素的子集，所以会是O(M*LogN)。。你的2分，是在M个元素中二分，找出一个最小的合适元素curr，使得最后K元素子集的半径为X,所以复杂度是O(K*logM).
: 从你得到的总复杂度来看，你还是对X的范围进行了二分的，所以才会有LogN.
: 你最后得到的复杂度，其实是已经在两次二分的基础上得到的（对0..M一次，对0..N一次）， 所以总复杂度等于sort的复杂度+O(k*logM*logN).
: 我自己都快绕晕了。。
|
f******t
发帖数: 7283 | 20 用上抽屉原理这道题就简单很多了：
M个数字里面要选K个，那就是说假如把这M个数字分成K-1份，不管你怎么选那K个数，
其中至少有2个是来自那K-1份中的其中某一份的。既然半径是定义为distance最小的，
那处在“同一份”里的数就有可能构成最小距离喽（比如说，用均值不等式）。问题就
转化为，怎么分那K-1份？解决这个并不难，我记得多年前在某市的奥数竞赛二试题里
有过这个题，既然那时候都是人脑算答案的，所以我觉得其实这道题不一定要写程序才
能算出结果。
临睡前一分钟随便想到的东东，我不保证一定100%对哦。 |
|
|
A*********r
发帖数: 564 | 21 嗯，对的，他实现的是在M上的二分查找，不过跟我在DP版本给出的思路不太一样，也
不能直接用在那里。
不知道他给出的code到底针对的是DP版本还是非DP版本，呵呵。。
【在 h**k 的大作中提到】
: han6就是实现的你改进的DP算法的最后的那个二分查找。他是想说明这里用线性查找和
: 二分查找效率差不多。
:
: 集，所以会是O(M*LogN)。。你的2分，是在M个元素中二分，找出一个最小的合适元素
: curr，使得最后K元素子集的半径为X,所以复杂度是O(K*logM).
: 一次）， 所以总复杂度等于sort的复杂度+O(k*logM*logN).
|
h**6
发帖数: 4160 | 22 我其实是回你上一个帖子：
“有一点想不通，如何只用O(M)判断是否能找到K个元素，使得他们之间的最小距离大
于等于给定的X？”
给出两个版本的代码，分别是O(M)和O(KlogM)复杂度。
两个函数的声明完全相同
bool findelements(int* a, int M, int K, int x)
判断已排序的长度为 M 的数组 a 中，是否存在 K 个元素的子集，其半径不小于 x ，返回值
为 bool 类型。 |
A*********r
发帖数: 564 | 23 haha, everything make sense now.
Thanks for clarification.
，返回值
【在 h**6 的大作中提到】
: 我其实是回你上一个帖子：
: “有一点想不通，如何只用O(M)判断是否能找到K个元素，使得他们之间的最小距离大
: 于等于给定的X？”
: 给出两个版本的代码，分别是O(M)和O(KlogM)复杂度。
: 两个函数的声明完全相同
: bool findelements(int* a, int M, int K, int x)
: 判断已排序的长度为 M 的数组 a 中，是否存在 K 个元素的子集，其半径不小于 x ，返回值
: 为 bool 类型。
|
k*******n
发帖数: 8891 | |
