搜狐2012牛逼笔试题，至今无思路，求牛人指点

hbmhalley

回复 60# cjaizss


    求链接

cjaizss

.............
    不用看,学了这么多年的计算理论我连这个都没明白就是白学了.
    我把计算理 ...
cjaizss 发表于 2011-12-04 12:06

   

hbmhalley

回复 51# cjaizss


    囧 . 我没看到这层楼..   原来是EXPTIME我一直以为NPC是最强的呵呵我错了
    不过背包真的是那么定义的么

hbmhalley

回复 62# cjaizss


    那我是不是被坑了 .. 你去把wiki改了吧

cjaizss

回复  cjaizss


    那我是不是被坑了 .. 你去把wiki改了吧
hbmhalley 发表于 2011-12-04 12:11

    懒得改了,要真正去了解并要做算法分析的人,他们请教的是数学课本,不是wiki

hbmhalley

回复 65# cjaizss


    学习了

cjaizss

回复  cjaizss


    学习了
hbmhalley 发表于 2011-12-04 12:15

    再给你一个包含的关系
  P,NP,NPH,PSCACE,EXPTIME
  以上,前面是后面的子集
未解决的问题:
以上每一级是否真包含(集合真包含的意思就是除了它,外面是否还有元素)   
NPC是最难的NP
PSPACE-C是最难的PSPACE
NPC是NP的一个子集
如果我们有天发现P=NP
那么,P,NP,NPC是三个完全一模一样的集合
PSPACE-C也是
PSPACE可能大家比较陌生,那是在多项式空间可以解决

kf38211

此题其实很简单，没有那么复杂，复杂度就是N。

假设集合为  {N(1), N(2) ,N(3), ..., N(n)}

假设符合条件的结果集为{N(i), N(i+1), ..., N(i+k-2), N(i+k-1)}

则有：
|N(i)-M| + ... +|N(i+k-1)-M| <= |N(i+1)-M| + ... + |N(i+k)-M|
且
|N(i)-M| + ... +|N(i+k-1)-M| <= |N(i-1)-M| + ... + |N(i+k-2)-M|

化简为：
N(i) + N(i+k)  >= 2M
且
N(i+k-1) + N(i-1) <= 2M

所以本题即是求使得  N(i) + N(i+k)  >= 2M   成立 且   N(i+k-1) + N(i-1) <= 2M  成立的 i 值（k表示“若干”）

所以只需要一个for循环足以。

关键是此题是有序集合，如果是无序集合，那么可能会存在多个 i 值，则还要对这多个 i 值对应的结果集计算最小值。