b*2
2 楼
这两天没什么动静，没见到绿的。
m*o
3 楼
钱是父亲投资在亲戚那里的，然后从亲戚的账号汇出的。当时为了省事直接请自己父亲
签了gift letter。现在办贷款的人要求看当时的汇款账号和户主，银行应该会发现来
源不是自己父亲，（亲戚是父亲的弟弟，名字查了一个字）。现在不知道有没有什么办
法解释清楚？
另外，当时汇了3万块，其中2.3万以及用来cash付款买了车，剩下0.7万还在自己账上
。不知道能不能和银行claim钱其实是用来买车的？银行会允许吗？
签了gift letter。现在办贷款的人要求看当时的汇款账号和户主，银行应该会发现来
源不是自己父亲，（亲戚是父亲的弟弟，名字查了一个字）。现在不知道有没有什么办
法解释清楚？
另外，当时汇了3万块，其中2.3万以及用来cash付款买了车，剩下0.7万还在自己账上
。不知道能不能和银行claim钱其实是用来买车的？银行会允许吗？
I*g
4 楼
DP 不是 群P 就可以。
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
m*o
5 楼
请大牛指教！
o*p
7 楼
能等下个月干净银行帐单吗？
【在 m*******o 的大作中提到】
: 钱是父亲投资在亲戚那里的，然后从亲戚的账号汇出的。当时为了省事直接请自己父亲
: 签了gift letter。现在办贷款的人要求看当时的汇款账号和户主，银行应该会发现来
: 源不是自己父亲，（亲戚是父亲的弟弟，名字查了一个字）。现在不知道有没有什么办
: 法解释清楚？
: 另外，当时汇了3万块，其中2.3万以及用来cash付款买了车，剩下0.7万还在自己账上
: 。不知道能不能和银行claim钱其实是用来买车的？银行会允许吗？
【在 m*******o 的大作中提到】
: 钱是父亲投资在亲戚那里的，然后从亲戚的账号汇出的。当时为了省事直接请自己父亲
: 签了gift letter。现在办贷款的人要求看当时的汇款账号和户主，银行应该会发现来
: 源不是自己父亲，（亲戚是父亲的弟弟，名字查了一个字）。现在不知道有没有什么办
: 法解释清楚？
: 另外，当时汇了3万块，其中2.3万以及用来cash付款买了车，剩下0.7万还在自己账上
: 。不知道能不能和银行claim钱其实是用来买车的？银行会允许吗？
g*v
8 楼
说实话，这题真心难。
m*o
9 楼
等不了啊，房子定在下个月底close。除非这个不买了，再去找下一个
r*7
10 楼
DP
当前处理的人要么和一个人是情侣，要么不是，不是直接向后走
是的话，有两个candidate的位置可以选，try哪边小
n^3的DP，不知道有没有更简单的了
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
当前处理的人要么和一个人是情侣，要么不是，不是直接向后走
是的话，有两个candidate的位置可以选，try哪边小
n^3的DP，不知道有没有更简单的了
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
c*7
11 楼
可以等，先提交别的材料。等statement出来再补充,remove condition。
【在 m*******o 的大作中提到】
: 等不了啊，房子定在下个月底close。除非这个不买了，再去找下一个
【在 m*******o 的大作中提到】
: 等不了啊，房子定在下个月底close。除非这个不买了，再去找下一个
M*7
12 楼
麻烦大神写一下递推式。
想了一下总觉得子问题不独立，因为假设子问题某区排好序但元素又不一定固定。
加上像下面这种需要把一对情侣都换出来的情况实在是想不清楚了。
（同字母代表一对情侣，空格不是空位，只是为了看起来方便，D 是分开的情侣，X Y
单身）
AABBCC D EEFFGG D HHIIJJKKLLMM X Y
多谢！
【在 r****7 的大作中提到】
: DP
: 当前处理的人要么和一个人是情侣，要么不是，不是直接向后走
: 是的话，有两个candidate的位置可以选，try哪边小
: n^3的DP，不知道有没有更简单的了
想了一下总觉得子问题不独立，因为假设子问题某区排好序但元素又不一定固定。
加上像下面这种需要把一对情侣都换出来的情况实在是想不清楚了。
（同字母代表一对情侣，空格不是空位，只是为了看起来方便，D 是分开的情侣，X Y
单身）
AABBCC D EEFFGG D HHIIJJKKLLMM X Y
多谢！
【在 r****7 的大作中提到】
: DP
: 当前处理的人要么和一个人是情侣，要么不是，不是直接向后走
: 是的话，有两个candidate的位置可以选，try哪边小
: n^3的DP，不知道有没有更简单的了
b*b
13 楼
跟银行实话实说吧---说签 Gift letter 的人找错了--不用解释太多，就说是找错了，
然后找亲戚重新写个gift letter. 银行不是FBI，他们只要材料 match 就好了。
（其实还是你父亲签字，签你家亲戚的名字呗---有的银行你只要寄钱的自己写歌证明）
有的美国银行要中国银行的official gift letter. 所以，买房子找对银行很重要。
【在 m*******o 的大作中提到】
: 等不了啊，房子定在下个月底close。除非这个不买了，再去找下一个
然后找亲戚重新写个gift letter. 银行不是FBI，他们只要材料 match 就好了。
（其实还是你父亲签字，签你家亲戚的名字呗---有的银行你只要寄钱的自己写歌证明）
有的美国银行要中国银行的official gift letter. 所以，买房子找对银行很重要。
【在 m*******o 的大作中提到】
: 等不了啊，房子定在下个月底close。除非这个不买了，再去找下一个
l*8
14 楼
greedy
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
m*o
15 楼
那gift可以从自己的叔叔来吗？不是一定要直系亲属？十分感谢！
h*c
16 楼
假设六个人
有p 6 6 坐法
情侣坐有 p 3 3 * 2 法
因为是个permutation group，可以markov chain 反算当前状态
有p 6 6 坐法
情侣坐有 p 3 3 * 2 法
因为是个permutation group，可以markov chain 反算当前状态
b*b
17 楼
当然可以。 gift 可以从路人那里来，只要有人愿意给你钱。
呵呵呵！
我不是做贷款的－－－现在准备自己考个ｌｉｃｅｎｓｅ了，但是知道一些。 请版上
做贷款的来给标准答案。
【在 m*******o 的大作中提到】
: 那gift可以从自己的叔叔来吗？不是一定要直系亲属？十分感谢！
呵呵呵！
我不是做贷款的－－－现在准备自己考个ｌｉｃｅｎｓｅ了，但是知道一些。 请版上
做贷款的来给标准答案。
【在 m*******o 的大作中提到】
: 那gift可以从自己的叔叔来吗？不是一定要直系亲属？十分感谢！
M*7
18 楼
包子求好方法。
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
m*o
19 楼
啊，原来如此，十分感谢！
h*c
20 楼
这个 题
如果有m对情侣，假设坐满，假设全是情侣n
那么正确做法坐法应该有 p m m * ２, hashmap or list
当前坐法 string diff 正确做法，实际上string diff就是两个矢量差normal form。
比distance 最小的一个出来，然后折腾
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
如果有m对情侣，假设坐满，假设全是情侣n
那么正确做法坐法应该有 p m m * ２, hashmap or list
当前坐法 string diff 正确做法，实际上string diff就是两个矢量差normal form。
比distance 最小的一个出来，然后折腾
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
c*e
21 楼
最好的方法就是重新签一封Gift Letter，再写封信解释一下之前的Gift Letter写错了
。银行不会因为一封错误的Gift Letter而deny贷款。叔叔可以是Gift Fund的提供者。
Gift只要是血亲都能提供，同事朋友则不行。
【在 m*******o 的大作中提到】
: 钱是父亲投资在亲戚那里的，然后从亲戚的账号汇出的。当时为了省事直接请自己父亲
: 签了gift letter。现在办贷款的人要求看当时的汇款账号和户主，银行应该会发现来
: 源不是自己父亲，（亲戚是父亲的弟弟，名字查了一个字）。现在不知道有没有什么办
: 法解释清楚？
: 另外，当时汇了3万块，其中2.3万以及用来cash付款买了车，剩下0.7万还在自己账上
: 。不知道能不能和银行claim钱其实是用来买车的？银行会允许吗？
。银行不会因为一封错误的Gift Letter而deny贷款。叔叔可以是Gift Fund的提供者。
Gift只要是血亲都能提供，同事朋友则不行。
【在 m*******o 的大作中提到】
: 钱是父亲投资在亲戚那里的，然后从亲戚的账号汇出的。当时为了省事直接请自己父亲
: 签了gift letter。现在办贷款的人要求看当时的汇款账号和户主，银行应该会发现来
: 源不是自己父亲，（亲戚是父亲的弟弟，名字查了一个字）。现在不知道有没有什么办
: 法解释清楚？
: 另外，当时汇了3万块，其中2.3万以及用来cash付款买了车，剩下0.7万还在自己账上
: 。不知道能不能和银行claim钱其实是用来买车的？银行会允许吗？
e*2
22 楼
至少可以转化为minimum weight matching!所以有Polynomial time解。
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
【在 l*******i 的大作中提到】
: 一群朋友去电影院，有一些是情侣有一些不是，一开始都乱坐在同一排座位，要怎么样
: 用minimum swap把情侣排在一起
I*s
23 楼
看情况你的Gift Letter 已经给underwriting了，而且你实际不需要Gift 的钱来买房
子。建议如下：
1）提供汇款帐号和户主。
2）如果万一没被发现最好， 如果被发现就解释下然后让你叔叔签一封新的Gift
Letter。
3）不要claim是用来买车的，因为即使你claim也少不了前面的材料。
子。建议如下：
1）提供汇款帐号和户主。
2）如果万一没被发现最好， 如果被发现就解释下然后让你叔叔签一封新的Gift
Letter。
3）不要claim是用来买车的，因为即使你claim也少不了前面的材料。
c*m
24 楼
记录下相同两个字母出现的下标，组成一个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
动的次数为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
m*o
25 楼
谢谢上面各位给的建议，非常有帮助！
h*t
26 楼
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
【在 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
k*a
27 楼
gift fund一般要求是family member提供的。
i*e
28 楼
我觉得题目都没说清楚啊。
是只能相邻的两个swap还是随意swap?目标状态是给定的，也就是说AA必须在BB左面，
还是只要最后情侣们都在一起就行了？
是只能相邻的两个swap还是随意swap?目标状态是给定的，也就是说AA必须在BB左面，
还是只要最后情侣们都在一起就行了？
e*2
29 楼
情侣在一起就行了，任意两个都可以swap。
【在 i*********e 的大作中提到】
: 我觉得题目都没说清楚啊。
: 是只能相邻的两个swap还是随意swap?目标状态是给定的，也就是说AA必须在BB左面，
: 还是只要最后情侣们都在一起就行了？
【在 i*********e 的大作中提到】
: 我觉得题目都没说清楚啊。
: 是只能相邻的两个swap还是随意swap?目标状态是给定的，也就是说AA必须在BB左面，
: 还是只要最后情侣们都在一起就行了？
i*e
30 楼
想了一下，初步想法是用IDA*或者A*：
每次swap组合成的情侣可能值为0,1,2. 最优情况下每次swap至少应该组合一对情侣。
因为假设存在某种最优解，其中某次swap没有组合成任何一对情侣，那么其在最理想状
态下也是和一个组合成两对情侣的配对，即两次swap组合成两对，不可能比两次swap，
每次组合成一对更优。
这样每种状态下，可选的swap就减少了，我们可以依次序尝试组合成两对的，组合成一
对的，组合成一对又破坏了一对的。
估值函数为当前未配对的情侣对数/2.
===
我很怀疑这题有dp或者greedy的解法。可以参考poj2046或者uva 15-puzzle. 都是要用
智能搜索的。
每次swap组合成的情侣可能值为0,1,2. 最优情况下每次swap至少应该组合一对情侣。
因为假设存在某种最优解，其中某次swap没有组合成任何一对情侣，那么其在最理想状
态下也是和一个组合成两对情侣的配对，即两次swap组合成两对，不可能比两次swap，
每次组合成一对更优。
这样每种状态下，可选的swap就减少了，我们可以依次序尝试组合成两对的，组合成一
对的，组合成一对又破坏了一对的。
估值函数为当前未配对的情侣对数/2.
===
我很怀疑这题有dp或者greedy的解法。可以参考poj2046或者uva 15-puzzle. 都是要用
智能搜索的。
l*i
31 楼
我勒个去，没想到这题这么复杂，本来想问个DP的递推公式的。
GG店面都是这种难度了，丧心病狂
【在 i*********e 的大作中提到】
: 想了一下，初步想法是用IDA*或者A*：
: 每次swap组合成的情侣可能值为0,1,2. 最优情况下每次swap至少应该组合一对情侣。
: 因为假设存在某种最优解，其中某次swap没有组合成任何一对情侣，那么其在最理想状
: 态下也是和一个组合成两对情侣的配对，即两次swap组合成两对，不可能比两次swap，
: 每次组合成一对更优。
: 这样每种状态下，可选的swap就减少了，我们可以依次序尝试组合成两对的，组合成一
: 对的，组合成一对又破坏了一对的。
: 估值函数为当前未配对的情侣对数/2.
: ===
: 我很怀疑这题有dp或者greedy的解法。可以参考poj2046或者uva 15-puzzle. 都是要用
i*e
32 楼
我也不是很确定。不过无论dp还是greedy，都需要问题中又可以利用的“order”，我
实在是看不出来这里有什么order.
不过如果真的是电面题的话，也许真有什么trick可以很简单的解吧。即使这样，也很
变态了。
实在是看不出来这里有什么order.
不过如果真的是电面题的话，也许真有什么trick可以很简单的解吧。即使这样，也很
变态了。
M*7
33 楼
这个思路挺好的，的确很像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
我这里很可能断章取义了，因为看不太懂，不好意思哈。
一个空位可供交换的例如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
34 楼
连大牛都这么说了，看来只能等面经里面漏提示了。
如果现在遇到了只能上BFS了。
【在 i*********e 的大作中提到】
: 我也不是很确定。不过无论dp还是greedy，都需要问题中又可以利用的“order”，我
: 实在是看不出来这里有什么order.
: 不过如果真的是电面题的话，也许真有什么trick可以很简单的解吧。即使这样，也很
: 变态了。
如果现在遇到了只能上BFS了。
【在 i*********e 的大作中提到】
: 我也不是很确定。不过无论dp还是greedy，都需要问题中又可以利用的“order”，我
: 实在是看不出来这里有什么order.
: 不过如果真的是电面题的话，也许真有什么trick可以很简单的解吧。即使这样，也很
: 变态了。
h*t
35 楼
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.
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
36 楼
嗯，我没写清楚。
我的意思是每次swap必然要冲着可以凑成一对的目标去。但是如果凑成一对，拆散一对
也可以。但是什么都没有凑成的话是不行的。就是说
ABCBCDDEEA->
BACBCDDEEA
这种显然没意义，哪怕最后总数不变。
我觉得这题比15puzzle难啊，15puzzle每步就四种可能，这里就难说了。
我的意思是每次swap必然要冲着可以凑成一对的目标去。但是如果凑成一对，拆散一对
也可以。但是什么都没有凑成的话是不行的。就是说
ABCBCDDEEA->
BACBCDDEEA
这种显然没意义，哪怕最后总数不变。
我觉得这题比15puzzle难啊，15puzzle每步就四种可能，这里就难说了。
i*e
37 楼
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.
.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
38 楼
顺序扫描第i * 2的节点，如果i * 2 + 1的节点和i * 2节点配对则，跳过去到(i * 2
+ 2)处，否则把与(i * 2)匹配的节点交换过来。复杂度为O（n）。
+ 2)处，否则把与(i * 2)匹配的节点交换过来。复杂度为O（n）。
U*A
39 楼
这个想法是不是很不靠谱，有点像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中的小的一个。
例如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
40 楼
明白了。谢谢解释。
是啊， 这里一步的可能很多。
【在 i*********e 的大作中提到】
: 嗯，我没写清楚。
: 我的意思是每次swap必然要冲着可以凑成一对的目标去。但是如果凑成一对，拆散一对
: 也可以。但是什么都没有凑成的话是不行的。就是说
: ABCBCDDEEA->
: BACBCDDEEA
: 这种显然没意义，哪怕最后总数不变。
: 我觉得这题比15puzzle难啊，15puzzle每步就四种可能，这里就难说了。
是啊， 这里一步的可能很多。
【在 i*********e 的大作中提到】
: 嗯，我没写清楚。
: 我的意思是每次swap必然要冲着可以凑成一对的目标去。但是如果凑成一对，拆散一对
: 也可以。但是什么都没有凑成的话是不行的。就是说
: ABCBCDDEEA->
: BACBCDDEEA
: 这种显然没意义，哪怕最后总数不变。
: 我觉得这题比15puzzle难啊，15puzzle每步就四种可能，这里就难说了。
M*7
41 楼
这个观察不错，就是头尾的对子可以拿掉。
可算法上好像还是有问题，像以下这种情况，要交换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）。
可算法上好像还是有问题，像以下这种情况，要交换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
42 楼
这题比较讨厌的就是有单身的存在。
所以有可能
<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
所以有可能
<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
相关阅读
买房时大家会介意门牌号带4的吗？看急诊真是要命洗衣机的rinse功能closing to close，有什么特别注意的么？Dish那个天线有没有办法利用一下？Angel List要Membership？请大家推荐个去水垢的东西打印机的墨水怎么清洁?紧急求助，这满满一缸水的hot tub应该怎么处理1951年的房子可以买吗？miter saw房子二选一说别的都是假的请问地毯换地板如何开价foreclosure后被中间商低价买进的resale的房子？求好用的Granite与瓷砖Grout的Sealer【多图】：冰箱 冰块通道 老堵塞 永久除根修理这款洗油烟机，炉头清洁剂请几位外州的同学不要讨论“城里”“乡下”了壁炉太多会不会有坏处？