再问道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

再问道题

再问道题# JobHunting - 待字闺中

P*b2010-08-30 07:08

1 楼

这里牛人多
You are given an array of positive integers. Convert it to a sorted array wi
th minimum cost. Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of element
For example:
4,3,5,6, -> cost 1
10,3,11,12 -> cost 3
代码总写不好

h*62010-08-30 07:08

2 楼

这个decrement指的是减几啊？还是随便换成任意一个更小的数？
可不可以把不合条件的数全部变成0，然后再remove掉，这样cost比较小哦。

P*b2010-08-30 07:08

3 楼

从例子看，减到和后面的相等

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

: 这个decrement指的是减几啊？还是随便换成任意一个更小的数？
: 可不可以把不合条件的数全部变成0，然后再remove掉，这样cost比较小哦。

h*k2010-08-30 07:08

4 楼

老题，似乎是facebook考过的题。DP解法。

wi

【在 P*******b 的大作中提到】

: 这里牛人多
: You are given an array of positive integers. Convert it to a sorted array wi
: th minimum cost. Only valid operation are
: 1) Decrement -> cost = 1
: 2) Delete an element completely from the array -> cost = value of element
: For example:
: 4,3,5,6, -> cost 1
: 10,3,11,12 -> cost 3
: 代码总写不好

t*a2010-08-30 07:08

5 楼

简单想法：
定义An, An+1为问题pair当An > An+1
1、删掉一个数字，仅发生在An+1上
2、把数字变小，仅发生在An上
3、操作顺序可规范为，先删去一些数字，再减小一些数字
据此可以写一个最优解的搜索算法
1、假定共需要删掉0，1，.,..n个数字
2、在每种情况下搜最优解，搜索过程中剪枝

f*k2010-08-30 07:08

6 楼

O(n^3) dp, 貌似可以优化到n^2

p*72010-08-30 07:08

7 楼

用个stack记录，保持一个当前修改成本，当前删除成本，已经总成本
如果数据大于stack的top就压入，如果小于就pop出stack数据直到top<=数据
在pop过程中计算修改成本
比如 4，6，3，3，5，9，4
本来stack里面似乎4，6，后来3来了，修改成本是1+3 = 4.删除成本是3，所以删除，
然后又来个三，这个时候stack还没加入新的数，修改成本没变，删除成本变为6了，于
是选择修改，stack里面是3，3，并且加入2个新的3，3就成3，3，3，3。重置当前删除
成本以及当前修改成本，更新总成本为4
下面压入5，9。stack是3，3，3，3，5，9
最后是4，弹出9，5，修改成本是5，删除成本是4，选择删除。总成本就是4+4=8.

K*g2010-08-30 07:08

8 楼

“然后又来个三，这个时候stack还没加入新的数，修改成本没变，删除成本变为6了，
”这个说起来容易，你怎么code？
很显然，后面新加的数对前面的“最优解”是有影响的，这道题目好像也不能用DP，因
为大规模的最优解不是建立与小规模的最优解基础上，而且是相互影响的。用greedy的
方法做出来的又不是最优解。
举个例子：
4 6 3 6 4
4，6加进去后，3进来，修改的成本为4，删除的成本为3，选择删除；
6进来，不需要成本，序列为4 6 6
4进来，删除成本是4，修改成本是4，最后的序列是4 4 4 4，总成本是3+4=7
如果4进来的时候，重新考虑3，我们不删除3，选择修改，序列变成3 3 3，成本是4.当
4进来的时候，序列为3 3 3 6 4，选择修改，变成3 3 3 4 4，所以总成本是4+2=6

【在 p********7 的大作中提到】

: 用个stack记录，保持一个当前修改成本，当前删除成本，已经总成本
: 如果数据大于stack的top就压入，如果小于就pop出stack数据直到top<=数据
: 在pop过程中计算修改成本
: 比如 4，6，3，3，5，9，4
: 本来stack里面似乎4，6，后来3来了，修改成本是1+3 = 4.删除成本是3，所以删除，
: 然后又来个三，这个时候stack还没加入新的数，修改成本没变，删除成本变为6了，于
: 是选择修改，stack里面是3，3，并且加入2个新的3，3就成3，3，3，3。重置当前删除
: 成本以及当前修改成本，更新总成本为4
: 下面压入5，9。stack是3，3，3，3，5，9
: 最后是4，弹出9，5，修改成本是5，删除成本是4，选择删除。总成本就是4+4=8.

h*k2010-08-30 07:08

9 楼

是可以用动态规划来做的。实际上是记录之前的各种情况下的最优解。下面试着解释一
下思路。
1。f(n)为在只考虑前n个数字，并且第n个数字出现在输出序列中（即它的值没有降低)
的情况下的最小cost。(注意，f(n)并不一定是前n个数字的最小cost，因为最后一个数
字可以不出现在最优解中）
比如对于输入 4 3 5 2 6 1
f(1) = 0
f(2) = 1 (输出序列是3 3 ）
f(3) = 1 (输出序列是3 3 5）
f(4) = 6 (输出序列是2 2 2 2）
f(5) = 3 (输出序列是3 3 5 6）
f(6) = 15 (输出序列是1 1 1 1 1 1）
2。已知f(i)，1<=i<=n-1，可以计算f(n)的值。基本思想是假设之前的一个输出元素是
a[i]，则可以计算利用f(i)来计算在这种情况下的cost。对于所有的i,1<=i<=n-1，我
们都可以计算出一种可能的cost，从中选择最小的cost作为f(n)的值。
现在问题变成已知输出数组的两个元素来至a[i]和a[n]，并且已知f(i)，如何计算f(n)
。这里需要考虑两种情况：
case

【在 K******g 的大作中提到】

: “然后又来个三，这个时候stack还没加入新的数，修改成本没变，删除成本变为6了，
: ”这个说起来容易，你怎么code？
: 很显然，后面新加的数对前面的“最优解”是有影响的，这道题目好像也不能用DP，因
: 为大规模的最优解不是建立与小规模的最优解基础上，而且是相互影响的。用greedy的
: 方法做出来的又不是最优解。
: 举个例子：
: 4 6 3 6 4
: 4，6加进去后，3进来，修改的成本为4，删除的成本为3，选择删除；
: 6进来，不需要成本，序列为4 6 6
: 4进来，删除成本是4，修改成本是4，最后的序列是4 4 4 4，总成本是3+4=7

t*a2010-08-30 07:08

10 楼

Very cool solution.
has a minor bug here:
case 1: a[i] <= a[n]，这个简单，我们要把a[n]加到已经存在的输出数组上，只需要
处理a[i] 到 a[n]中间的所有元素。对于每个a[j]，i只需把它降到a[n]，就可以同样输出；如果小于a[n]，则需要降到0。因此，我们定义
这么一个辅助函数
如果他大于a[n] should be 如果他大于a[i], right?
same as 如果小于a[n].

低)

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

: 是可以用动态规划来做的。实际上是记录之前的各种情况下的最优解。下面试着解释一
: 下思路。
: 1。f(n)为在只考虑前n个数字，并且第n个数字出现在输出序列中（即它的值没有降低)
: 的情况下的最小cost。(注意，f(n)并不一定是前n个数字的最小cost，因为最后一个数
: 字可以不出现在最优解中）
: 比如对于输入 4 3 5 2 6 1
: f(1) = 0
: f(2) = 1 (输出序列是3 3 ）
: f(3) = 1 (输出序列是3 3 5）
: f(4) = 6 (输出序列是2 2 2 2）

h*k2010-08-30 07:08

11 楼

这里没错，应该是大于a[n]，后面那个应该是小于a[i]。考虑这个例子，输入数组是 1
2 3 2 4 6 5
现在用f(3)计算f(7)，a[7] = 4 〉a[3] = 3；
对于f(3)，已经输出的数组是1 2 3，现在要加入a[7]进入输出，那么如何处理a[4]，a
[5]，a[6]？a[6]>a[7]，所以必须减到a[7]；a[4]n]之间，不需要处理，直接加入数组就可以。

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

: Very cool solution.
: has a minor bug here:
: case 1: a[i] <= a[n]，这个简单，我们要把a[n]加到已经存在的输出数组上，只需要
: 处理a[i] 到 a[n]中间的所有元素。对于每个a[j]，i: 只需把它降到a[n]，就可以同样输出；如果小于a[n]，则需要降到0。因此，我们定义
: 这么一个辅助函数
: 如果他大于a[n] should be 如果他大于a[i], right?
: same as 如果小于a[n].
:
: 低)

p*72010-08-30 07:08

12 楼

我确实没考虑清楚

【在 K******g 的大作中提到】