l*******i
发帖数: 57 | 1 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
用minimum swap把情侣排在一起 |
I*******g
发帖数: 7600 | 2 DP 不是 群P 就可以。
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
|
w**********o
发帖数: 140 | |
g****v
发帖数: 971 | |
r****7
发帖数: 2282 | 5 DP
当前处理的人要么和一个人是情侣，要么不是，不是直接向后走
是的话，有两个candidate的位置可以选，try哪边小
n^3的DP，不知道有没有更简单的了
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
|
M**********7
发帖数: 378 | 6 麻烦大神写一下递推式。
想了一下总觉得子问题不独立，因为假设子问题某区排好序但元素又不一定固定。
加上像下面这种需要把一对情侣都换出来的情况实在是想不清楚了。
（同字母代表一对情侣，空格不是空位，只是为了看起来方便，D 是分开的情侣，X Y
单身）
AABBCC D EEFFGG D HHIIJJKKLLMM X Y
多谢！
【在 r****7 的大作中提到】
: DP
: 当前处理的人要么和一个人是情侣，要么不是，不是直接向后走
: 是的话，有两个candidate的位置可以选，try哪边小
: n^3的DP，不知道有没有更简单的了
|
l*****8
发帖数: 1083 | 7 greedy
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
|
h**********c
发帖数: 4120 | 8 假设六个人
有p 6 6 坐法
情侣坐有 p 3 3 * 2 法
因为是个permutation group，可以markov chain 反算当前状态 |
M**********7
发帖数: 378 | 9 包子求好方法。
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
|
h**********c
发帖数: 4120 | 10 这个 题
如果有m对情侣，假设坐满，假设全是情侣n
那么正确做法坐法应该有 p m m * ２, hashmap or list
当前坐法 string diff 正确做法，实际上string diff就是两个矢量差normal form。
比distance 最小的一个出来，然后折腾
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
|
|
|
e********2
发帖数: 495 | 11 至少可以转化为minimum weight matching!所以有Polynomial time解。
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
|
c*****m
发帖数: 271 | 12 记录下相同两个字母出现的下标，组成一个pair，要使得这两个字母相近，要移
动的次数为t-s-1；
有很多个这样的pair，于是总的移动次数为各pair移动次数之和。
但是如果有两个pair的下标有交叉，如abab，对应的两个pair为<0,2>,<1,3>，两个
pair交叉，于是移动次数会省去一次。总移动次数为1+1-1=1;再如,abcabc，总移动次
数为3次，因为三个pair都相互有交叉。
于是算法为：
1.得到所有的pair，算出所有pair移动次数之和x, 复杂度O(n)
2.算出所有pair之间交叉的个数y，复杂度O(n^2)
结果为x-y |
h****t
发帖数: 69 | 13 you can swap with any position, not just between adjacent people
【在 c*****m 的大作中提到】
: 记录下相同两个字母出现的下标，组成一个pair，要使得这两个字母相近，要移
: 动的次数为t-s-1；
: 有很多个这样的pair，于是总的移动次数为各pair移动次数之和。
: 但是如果有两个pair的下标有交叉，如abab，对应的两个pair为<0,2>,<1,3>，两个
: pair交叉，于是移动次数会省去一次。总移动次数为1+1-1=1;再如,abcabc，总移动次
: 数为3次，因为三个pair都相互有交叉。
: 于是算法为：
: 1.得到所有的pair，算出所有pair移动次数之和x, 复杂度O(n)
: 2.算出所有pair之间交叉的个数y，复杂度O(n^2)
: 结果为x-y
|
i*********e
发帖数: 21 | 14 我觉得题目都没说清楚啊。
是只能相邻的两个swap还是随意swap?目标状态是给定的，也就是说AA必须在BB左面，
还是只要最后情侣们都在一起就行了？ |
e********2
发帖数: 495 | 15 情侣在一起就行了，任意两个都可以swap。
【在 i*********e 的大作中提到】
: 我觉得题目都没说清楚啊。
: 是只能相邻的两个swap还是随意swap?目标状态是给定的，也就是说AA必须在BB左面，
: 还是只要最后情侣们都在一起就行了？
|
i*********e
发帖数: 21 | 16 想了一下，初步想法是用IDA*或者A*：
每次swap组合成的情侣可能值为0,1,2. 最优情况下每次swap至少应该组合一对情侣。
因为假设存在某种最优解，其中某次swap没有组合成任何一对情侣，那么其在最理想状
态下也是和一个组合成两对情侣的配对，即两次swap组合成两对，不可能比两次swap，
每次组合成一对更优。
这样每种状态下，可选的swap就减少了，我们可以依次序尝试组合成两对的，组合成一
对的，组合成一对又破坏了一对的。
估值函数为当前未配对的情侣对数/2.
===
我很怀疑这题有dp或者greedy的解法。可以参考poj2046或者uva 15-puzzle. 都是要用
智能搜索的。 |
l*******i
发帖数: 57 | 17
我勒个去，没想到这题这么复杂，本来想问个DP的递推公式的。
GG店面都是这种难度了，丧心病狂
【在 i*********e 的大作中提到】
: 想了一下，初步想法是用IDA*或者A*：
: 每次swap组合成的情侣可能值为0,1,2. 最优情况下每次swap至少应该组合一对情侣。
: 因为假设存在某种最优解，其中某次swap没有组合成任何一对情侣，那么其在最理想状
: 态下也是和一个组合成两对情侣的配对，即两次swap组合成两对，不可能比两次swap，
: 每次组合成一对更优。
: 这样每种状态下，可选的swap就减少了，我们可以依次序尝试组合成两对的，组合成一
: 对的，组合成一对又破坏了一对的。
: 估值函数为当前未配对的情侣对数/2.
: ===
: 我很怀疑这题有dp或者greedy的解法。可以参考poj2046或者uva 15-puzzle. 都是要用
|
i*********e
发帖数: 21 | 18 我也不是很确定。不过无论dp还是greedy，都需要问题中又可以利用的“order”，我
实在是看不出来这里有什么order.
不过如果真的是电面题的话，也许真有什么trick可以很简单的解吧。即使这样，也很
变态了。 |
M**********7
发帖数: 378 | 19 这个思路挺好的，的确很像15-puzzle，不过这个可能比那个简单，有点像那种中心有
一个空位可供交换的例如8-puzzle。
分析的部分有点不懂：
：每次swap组合成的情侣可能值为0,1,2. 最优情况下每次swap至少应该组合一对情侣。
这里说的“优情况下每次swap至少应该组合一对情侣”是指组合成的情侣总数加一，还
是只是有一个新的组合产生，而不管是否破坏的情况？
如果是指组合成的情侣总数加一，下面这种情况就不满足：
A BB CC DD EE A ->
A AB CC DD EE B ->
A AB BC DD EE C ->
A AB BC CD EE D ->
A AB BC CD DE E
4次移动只加了一对。
：不可能比两次swap，每次组合成一对更优
ABAB ->
AABB
一次交换可以凑2对。
：我们可以依次序尝试组合成两对的，组合成一
如下这种情况，把两个A和X Y对调，单次swap就不产生任何组合，或者是看2步？
A BB CC DD EE A FF GG HH II JJ KK X Y
我这里很可能断章取义了，因为看不太懂，不好意思哈。 |
M**********7
发帖数: 378 | 20 连大牛都这么说了，看来只能等面经里面漏提示了。
如果现在遇到了只能上BFS了。
【在 i*********e 的大作中提到】
: 我也不是很确定。不过无论dp还是greedy，都需要问题中又可以利用的“order”，我
: 实在是看不出来这里有什么order.
: 不过如果真的是电面题的话，也许真有什么trick可以很简单的解吧。即使这样，也很
: 变态了。
|
|
|
h****t
发帖数: 69 | 21 Greedy如何？Implementation就先不纠结了，纯粹的 algo perspective
Def: Freedom score of any unpaired single is the number of adjacent seats
that is not currently occupied by a paired couple.
Swap顺序：
1) Make two pairs
2) Make one pair
2.1) Prioritize unpaired single with low freedom score
3) Can't make any pair, swap to increase freedom score.
4) Can't make any pair or increase freedom score, then swap to reduce total
distance between unpaired singles. |
i*********e
发帖数: 21 | 22 嗯，我没写清楚。
我的意思是每次swap必然要冲着可以凑成一对的目标去。但是如果凑成一对，拆散一对
也可以。但是什么都没有凑成的话是不行的。就是说
ABCBCDDEEA->
BACBCDDEEA
这种显然没意义，哪怕最后总数不变。
我觉得这题比15puzzle难啊，15puzzle每步就四种可能，这里就难说了。 |
i*********e
发帖数: 21 | 23 You have to prove any greedy approach...that is why i usually dont like it..
.i can never prove it unless it is a classic problem...
Yours is more like heuristic method, i dont see this prove its correctness.
You can combine this with intelligent search i mentioned though.
total
【在 h****t 的大作中提到】
: Greedy如何？Implementation就先不纠结了，纯粹的 algo perspective
: Def: Freedom score of any unpaired single is the number of adjacent seats
: that is not currently occupied by a paired couple.
: Swap顺序：
: 1) Make two pairs
: 2) Make one pair
: 2.1) Prioritize unpaired single with low freedom score
: 3) Can't make any pair, swap to increase freedom score.
: 4) Can't make any pair or increase freedom score, then swap to reduce total
: distance between unpaired singles.
|
u****w
发帖数: 4 | 24 顺序扫描第i * 2的节点，如果i * 2 + 1的节点和i * 2节点配对则，跳过去到(i * 2
+ 2)处，否则把与(i * 2)匹配的节点交换过来。复杂度为O（n）。 |
U***A
发帖数: 849 | 25 这个想法是不是很不靠谱，有点像greedy
例如7对couple，座位是
1 2 3 4 5 8 7 5 8 4 1 3 2 7
把他们看成7对，
<1 2> < 3 4 > < 5 8> <7 5> <8 4> <1 3> <2 7>
1。如果出现了两个数字相同的对，就直接删除。
2. 如果有两对含有相同的数字，交换一次之后删除。
3. 选第一对，找到一对中含有任何一个相同数字的对作交换，形成一对，删除。剩下
的一对和其他的对在进行类似的配对。假设这轮得到的交换次数为a.
第二轮，选下一对含有任何一个相同数字的对作交换，进行相同的配对。次数为b
然后取a，b中的小的一个。
|
M**********7
发帖数: 378 | 26 明白了。谢谢解释。
是啊， 这里一步的可能很多。
【在 i*********e 的大作中提到】
: 嗯，我没写清楚。
: 我的意思是每次swap必然要冲着可以凑成一对的目标去。但是如果凑成一对，拆散一对
: 也可以。但是什么都没有凑成的话是不行的。就是说
: ABCBCDDEEA->
: BACBCDDEEA
: 这种显然没意义，哪怕最后总数不变。
: 我觉得这题比15puzzle难啊，15puzzle每步就四种可能，这里就难说了。
|
M**********7
发帖数: 378 | 27 这个观察不错，就是头尾的对子可以拿掉。
可算法上好像还是有问题，像以下这种情况，要交换2和0位，就不是最优了。
0 1 2
A B B
2
【在 u****w 的大作中提到】
: 顺序扫描第i * 2的节点，如果i * 2 + 1的节点和i * 2节点配对则，跳过去到(i * 2
: + 2)处，否则把与(i * 2)匹配的节点交换过来。复杂度为O（n）。
|
M**********7
发帖数: 378 | 28 这题比较讨厌的就是有单身的存在。
所以有可能
<1 2> <2 3> <4 5> <5 6>
这样就算好了。
Hmm... 假设题目中没有单身的，全是couple的话，好像就变成停车位归位或者bucket
sort的题了。
b
【在 U***A 的大作中提到】
: 这个想法是不是很不靠谱，有点像greedy
: 例如7对couple，座位是
: 1 2 3 4 5 8 7 5 8 4 1 3 2 7
: 把他们看成7对，
: <1 2> < 3 4 > < 5 8> <7 5> <8 4> <1 3> <2 7>
: 1。如果出现了两个数字相同的对，就直接删除。
: 2. 如果有两对含有相同的数字，交换一次之后删除。
: 3. 选第一对，找到一对中含有任何一个相同数字的对作交换，形成一对，删除。剩下
: 的一对和其他的对在进行类似的配对。假设这轮得到的交换次数为a.
: 第二轮，选下一对含有任何一个相同数字的对作交换，进行相同的配对。次数为b
|
