※ 引述《colorflags ()》之铭言： : 我google了很久 不太知道要用什麽关键字 : 所以想请大家指点一下 : 问题是给一串数字 在k次相邻的swap里面找出最大的数值 : swap只能和隔壁的数字交换 : ex. 1 2 3 4 : 一次swap 就会是 2 1 3 4 : 两次swap 就是 3 1 2 4 这个数列内的数字会不会重复? (1) 如果不会重复，greedy 即可: 找出前 k+1 个数字中最大的 (假设是第 i 个)，把他换到第一个 (需要 i-1 次 swap) 如果还有剩下交换次数 k2，就递回下去处理，把 2~k2 间最大的换到第二个，依此类推 (2) 如果会重复，直觉上我会想 branch & bound: 找出前 k+1 数字中最大的那几个，把他们分别换到第一个，并继续递回下去... 但是，仔细想想会发现，其实用第一个方法就足够了。 (如果有多个最大值，选择出现较前者) 先写到这里，剩下的让大家先想想 :p (其实是英德大战要开始了 Orz) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 59.115.134.86 ※ 编辑: tkcn 来自: 140.122.183.199 (06/28 09:17)