photon回国用要解锁吗？ - 未名空间MITBBS历史存档

photon回国用要解锁吗？# PDA - 掌中宝

A*r2012-01-04 08:01

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(countelse min=x;
}
==================================

d*22012-01-04 08:01

2 楼

485 填表，　最后一次入境是加拿大　ＣＨＭ／ＮＹ，但没有任何证据，护照，１－２
０上都没有章
怎么处理，继续填写这个最后一次入境，还是有证据的上一次证据
Ｔｈａｎｋｓ

a*12012-01-04 08:01

3 楼

想下载点巫启贤的歌曲放在ipod里面送朋友，但是只有美国这边的IP，比如QQ音乐就不
能用。
也不知道去哪里可以免费下载，也不知道怎么弄到ipod上面，马上要过节了，买了个
ipod送朋友，但是里面要装点他喜欢的巫启贤的歌曲，请问有什么办法最简单，效率最
高吗？帮我解决问题的朋友，大包子的伺候，先谢谢啦。

d*n2012-01-04 08:01

4 楼

photon回国用要解锁吗？

t*a2012-01-04 08:01

5 楼

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];

w*n2012-01-04 08:01

6 楼

你要是就去加拿大玩几天回来,这个不算入境的

【在 d********2 的大作中提到】

: 485 填表，　最后一次入境是加拿大　ＣＨＭ／ＮＹ，但没有任何证据，护照，１－２
: ０上都没有章
: 怎么处理，继续填写这个最后一次入境，还是有证据的上一次证据
: Ｔｈａｎｋｓ

g*n2012-01-04 08:01

7 楼

http://mp3.sogou.com/music.so?query=%CE%D7%C6%F4%CF%CD&x=-905&y
进入页面以后选择"其他站点(286)"，虾米音乐好像需要付费下载。然后每首歌最右边
有下载箭头，你点击试试，不一定每首都能下载。我试了试，太傻和我没有钱我不要脸
能下载。
最后找个苹果产品用的熟练的帅哥帮你弄到ipod里面，省事儿。

h*k2012-01-04 08:01

8 楼

赞一个。最后使用的二分查找实在是太巧妙了。
另外，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];

d*22012-01-04 08:01

9 楼

我是为了登陆永久居民去的，只有一周的时间就回美国了，护照上有加拿大的签证与入
境章，但没有出境章，也没有美国的章．只是在ＬＺ的ＤＳ－２０１９上有美国的入境
章，ＬＰ的Ｆ１上什么也没有留下（曾经去过墨西哥签证Ｆ１，之上有墨西哥的章）

a*12012-01-04 08:01

10 楼

包子发了，下了很少几个曲子，不过还是很感激。

t*72012-01-04 08:01

11 楼

very good!

d*22012-01-04 08:01

12 楼

真的不用填了吗，加拿大也是国外呀，？？？

a*12012-01-04 08:01

13 楼

后来发现虾米下面的也可以下载选择稍微多些了没帅哥帮着转ipod，刚又上网问了朋
友，现在问题基本解决了。

A*r2012-01-04 08:01

14 楼

你的意思是直接用2分查找作，而不用DP？
能简单说一下思路吗？

【在 h**k 的大作中提到】

: 赞一个。最后使用的二分查找实在是太巧妙了。
: 另外，N是为了直接用二分查找来做这题的。
:
: DP.

w*n2012-01-04 08:01

15 楼

你都没说清楚你是怎么去加拿大,
去旅游的,没换i-94的不用填

【在 d********2 的大作中提到】

: 真的不用填了吗，加拿大也是国外呀，？？？

t*a2012-01-04 08:01

16 楼

han6 post his solution on the previous discussion

【在 A*********r 的大作中提到】

: 你的意思是直接用2分查找作，而不用DP？
: 能简单说一下思路吗？

d*22012-01-04 08:01

17 楼

开车去的，没有换I-94
是不是不用填去加拿大

h*k2012-01-04 08:01

18 楼

版上有人说过的。因为值域是1-N，所以solution的可能范围是0-N/k。对一个给定的值
x，我们很容易判断是否能找到k个元素，使得他们之间的最小距离大于等于x，这个判
断需要O(M)。注意，如果对于x不能找到这么k个元素，那么对于任何x'>x，都不可能找
到。这就构成了二分查找的判定条件，可以用二分查找找到最大的整数x，使得对于x我
们能发现k个元素。总的时间是O(MlogN)。

【在 A*********r 的大作中提到】

: 你的意思是直接用2分查找作，而不用DP？
: 能简单说一下思路吗？

w*n2012-01-04 08:01

19 楼

不用

【在 d********2 的大作中提到】

: 开车去的，没有换I-94
: 是不是不用填去加拿大

A*r2012-01-04 08:01

20 楼

谢谢，一门心思看dp, 忽略了他的帖子。。

【在 t****a 的大作中提到】

: han6 post his solution on the previous discussion

r*52012-01-04 08:01

21 楼

个人认为应该如实填写，不管有没有章。
请参考 http://international.tamu.edu/ISS/immigration/updateaddress.asp

【在 d********2 的大作中提到】

: 485 填表，　最后一次入境是加拿大　ＣＨＭ／ＮＹ，但没有任何证据，护照，１－２
: ０上都没有章
: 怎么处理，继续填写这个最后一次入境，还是有证据的上一次证据
: Ｔｈａｎｋｓ

A*r2012-01-04 08:01

22 楼

嗯，谢谢，这个比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*r2012-01-04 08:01

23 楼

有一点想不通，如何只用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*k2012-01-04 08:01

24 楼

greedy算法。

【在 A*********r 的大作中提到】

: 有一点想不通，如何只用O(M)判断是否能找到K个元素，使得他们之间的最小距离大于
: 等于给定的X？

A*r2012-01-04 08:01

25 楼

(根据建议，修改非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(countelse min=x;
}

【在 h**k 的大作中提到】

: greedy算法。

h*62012-01-04 08:01

26 楼

楼上的代码好像仍然不是很对，这是两个版本的代码，假设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*k2012-01-04 08:01

27 楼

你这个程序是直接用二分法找到最大的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*v2012-01-04 08:01

28 楼

不赞不行

寻找一个最大的半径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*r2012-01-04 08:01

29 楼

嗯，好像就是这个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*r2012-01-04 08:01

30 楼

我们两个的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*r2012-01-04 08:01

31 楼

自己顶一下，希望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*k2012-01-04 08:01

32 楼

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*t2012-01-04 08:01

33 楼

用上抽屉原理这道题就简单很多了：
M个数字里面要选K个，那就是说假如把这M个数字分成K-1份，不管你怎么选那K个数，
其中至少有2个是来自那K-1份中的其中某一份的。既然半径是定义为distance最小的，
那处在“同一份”里的数就有可能构成最小距离喽（比如说，用均值不等式）。问题就
转化为，怎么分那K-1份？解决这个并不难，我记得多年前在某市的奥数竞赛二试题里
有过这个题，既然那时候都是人脑算答案的，所以我觉得其实这道题不一定要写程序才
能算出结果。
临睡前一分钟随便想到的东东，我不保证一定100%对哦。

A*r2012-01-04 08:01

34 楼

嗯，对的，他实现的是在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*62012-01-04 08:01

35 楼

我其实是回你上一个帖子：
“有一点想不通，如何只用O(M)判断是否能找到K个元素，使得他们之间的最小距离大
于等于给定的X？”
给出两个版本的代码，分别是O(M)和O(KlogM)复杂度。
两个函数的声明完全相同
bool findelements(int* a, int M, int K, int x)
判断已排序的长度为 M 的数组 a 中，是否存在 K 个元素的子集，其半径不小于 x ，返回值
为 bool 类型。

A*r2012-01-04 08:01

36 楼

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*n2012-01-04 08:01

37 楼

re