S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Aug 30 00:32:06 2011, 美东) 提到:
Given an array A of positive integers. Convert it to a sorted array with
minimum cost. The only valid operation are:
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Aug 30 00:37:57 2011, 美东) 提到:
my 2 cents:
允许额外花费O(n)空间么。。。
允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
当前计数器值放入新开的等大小的数组中。
如果derement的代价是对所有元素为1的话，那cost是O(max(array))；否则是O(sum(ar
ray))
element
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Tue Aug 30 13:14:46 2011, 美东) 提到:
O(n2)的解
for (int i=n-1; i>0; i--) {
int price = 0;
// a[i] needs to be not less than all a[j] (0<=j
for (int j=0; j
if (a[j] > a[i]) price += a[j] - a[i];
}
if (price > a[i]) {
// remove a[i]
...
}
else {
// cut down all a[j]>a[i]
...
}
}
element
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Tue Aug 30 17:23:30 2011, 美东) 提到:
这个题目没看明白，貌似面试官想让你把排序开销和value大小挂钩。
可以维护一个linkedlist，每次每个元素减少1，一旦有一个元素减少到0，从
linkedlist里面取出插入到list前面，如此反复处理后面的数。
这样总体开销是所有元素的和。
但是，如果你自己直接比较大小，然后交换位置，可能开销更小，也就是说n^2可能比
上面这个算法cost小很多。
所以感觉题目很奇怪，不懂。
ar
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Tue Aug 30 17:28:51 2011, 美东) 提到:
肯定允许
题目要求你只能减少数字，如果不允许，那每个数都被减少的面目全非了，怎么复原？
ar
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Aug 30 17:36:48 2011, 美东) 提到:
careercup 's link
http://www.careercup.com/question?id=9333968
A indian give out a dp approach on this blog, but could not understand his
idea:
http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-valu
☆─────────────────────────────────────☆
dsp123 (dsppsd) 于 (Tue Aug 30 23:45:35 2011, 美东) 提到:
Try [5,2,2]
☆─────────────────────────────────────☆
anonymous1 (无名氏) 于 (Wed Aug 31 00:01:13 2011, 美东) 提到:
dp 吧
element
☆─────────────────────────────────────☆
dsp123 (dsppsd) 于 (Wed Aug 31 02:59:40 2011, 美东) 提到:
element
// {8,1,9,10,1}=2 {4,3,5,6}=1 {5,2,2,2,2}=3 {5,1,1,1,3,1}=5 {10,3,11,12}=3 {
5,3,5,3}=4
const int n = 4;
int a[n] = {5,3,5,3};
int dp[n+1], h[n+1];
dp[n] = 0;
h[n] = INT_MAX;
for (int i=n-1; i>-1; i--) {
dp[i] = INT_MAX;
for (int j=i+1; j
int tmp = (a[i]-h[j]>0)?(a[i]-h[j]):0;
for (int k=i+1; k
tmp += dp[j];
if (tmp
dp[i] = tmp;
h[i] = (j==n||a[i]
}
}
}
cout<<"COST = "<
Now O(n^3) time and O(n) space
Could be improved into O(n^2) time and O(n) space by using an aux array
☆─────────────────────────────────────☆
lonneman (每天老一点) 于 (Wed Aug 31 04:00:09 2011, 美东) 提到:
你这个怎么也不会是min cost
ar
☆─────────────────────────────────────☆
lonneman (每天老一点) 于 (Wed Aug 31 04:03:46 2011, 美东) 提到:
有没有insert？
element
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Wed Aug 31 12:55:05 2011, 美东) 提到:
这个题目到底什么意思啊，题目说only valid operation，就是说那些简单的比较，需
要的cost都是和数字大小有关，比如说if(ai>aj)，是不是不能直接比较，如果不能的
话，需要的cost是不是abs(ai-aj)，所以他要求的cost根本不是传统意义上的n^2, n^3
之类的啊。
要降低cost，就要降低比较的次数，这样对所有元素一起decrement到其中一个为0貌似
最好。
其他任何办法，不管怎么比较，至少O(nlogn)，但是每次比较都意味着O(ai)的开销，
那岂不是肯定开销很大？
element
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Wed Aug 31 12:58:47 2011, 美东) 提到:
为何不是，题目的only valid operation是什么意思？
☆─────────────────────────────────────☆
han6 (周瑜) 于 (Wed Aug 31 13:15:21 2011, 美东) 提到:
dp题，前n项以x结尾所需最小消耗为dp[n][x]
总复杂度为O(n*datarange^2)
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Wed Aug 31 13:20:42 2011, 美东) 提到:
能够详细讲讲思路？
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Wed Aug 31 13:29:25 2011, 美东) 提到:
恍然大悟，就是这个dp了。
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Wed Aug 31 14:02:59 2011, 美东) 提到:
看不懂
先问个简单问题，两个很大的数10000,9999，按照你的说法，cost就是2*1?
但是如何比较if(10000>9999)，把10000减少1和9999相等就行了？但是你怎么知道是减
少10000不是减少9999？另外，if(9999==9999)的开销又是多少？
我现在最不清楚的就是，if(ai>m)这样的操作是否需要cost，如果不需要，那岂不是直
接quick sort找pviot就行，quicksort不就是这么干的么，最后开销O(nlogn)
比如说http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-value-in-window-of.html这个里面的解法，就是假设(a[n] <= m) ?不需要开销，如果这个不需要开销，那用quicksort岂不是。。。。没有讨论的必要了。
☆─────────────────────────────────────☆
xeransis (nothing) 于 (Wed Aug 31 19:18:08 2011, 美东) 提到:
我的理解：
1.比较不算在cost里面，只有改变数组的操作算cost
2. 另外得到的数组应该不是原数组的排序。 对数组[10000， 9999] cost是1，只需要
把10000减1就得到9999,9999。
无法sort原数组，因为不可以增加任何元素的值。 无论是减少元素值还是移除元素，
都有cost，cost的值就是这个元素少掉的值，可以理解为为了达到递增的损耗。
3. 对每个元素，要决定是要除掉他还是减低一部分值。最后总的cost就是原数组的和
与得到数组的和的差值。 目的是使得这个差值最小，可以理解为损耗最小吧。
☆─────────────────────────────────────☆
nicebird (好鸟) 于 (Wed Aug 31 19:25:54 2011, 美东) 提到:
牛人好多。。
element
☆─────────────────────────────────────☆
tdaemon (jiang) 于 (Wed Aug 31 20:04:35 2011, 美东) 提到:
try {5,3,5,3,2}
{
☆─────────────────────────────────────☆
dsp123 (dsppsd) 于 (Wed Aug 31 22:41:12 2011, 美东) 提到:
Thanks for pointing out my error!
From your instance, I could see that my algorithm is completely wrong.
Need to rethink...
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Wed Aug 31 23:25:41 2011, 美东) 提到:
npc possible?
element
☆─────────────────────────────────────☆
returning (aaaaaaaaa) 于 (Thu Sep 1 00:22:55 2011, 美东) 提到:
http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-valu
我大概理解你的意思了，如果比较没有cost，而且无法直接sort数组，那么只能依次把
一个数删除掉这样来排序。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Sun Feb 26 14:04:42 2012, 美东) 提到:
昨天想了想，没想太明白。DP还是太弱了。
☆─────────────────────────────────────☆
hellobruce (大熊蛙 水上漂) 于 (Sun Feb 26 20:33:51 2012, 美东) 提到:
very basic undergraduate dp problem.
☆─────────────────────────────────────☆
Hbase (每天都进步一点点) 于 (Sun Feb 26 20:44:25 2012, 美东) 提到:
晕
说下思路？
☆─────────────────────────────────────☆
yuxingfan (yxf) 于 (Sun Feb 26 21:21:46 2012, 美东) 提到:
同意这个。
"Given an array A of positive integers. Convert it to a sorted array with
minimum cost."
这个题目就是说不能用赋值，swap等改变数值的操作。在A［i］原位置只能减，不能对
A［i］做其他任何改变数值的操作。通过挑出一些数来减（如果减到0就算删除了）构
造一个新的有序数列。这里的cost都不是算法意义上的cost，所以比较数值之类的运算
不会增加cost，cost只来源于两种允许的运算（其实只是一种，自减）。
比如
before: 1 7 2 14 13 12 12 19 25 20 18 13
12 15 8 5 4
ascending after: 1 7 0 12 12 12 12 15 15 15 15 0 0
15 0 0 0
total cost: 69
descending after: 0 0 0 0 0 0 0 19 19 19 18 13 12
12 8 5 4
total cost: 71
☆─────────────────────────────────────☆
hellobruce (大熊蛙 水上漂) 于 (Sun Feb 26 21:23:19 2012, 美东) 提到:
看了一下回帖，han6 的算法是对的。但是多了一维。 可以n*datarange做完。计算的
时候可以优化。
d[i][j] 存的是前i个，最后一个最高是j的时候的最优费用。 可以从d[i-1][*]算出来
。整个d[i][*]应该可以从d[i-1][*]用datarange时间算出来。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Sun Feb 26 22:09:35 2012, 美东) 提到:
能给个例子吗？我昨天按照这个思路做了做，不能做对。
☆─────────────────────────────────────☆
hellobruce (大熊蛙 水上漂) 于 (Sun Feb 26 22:22:08 2012, 美东) 提到:
你把程序贴一下。。。例子太麻烦了
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Sun Feb 26 22:26:38 2012, 美东) 提到:
总是发现有地方不对，改了之后，其他地方又不对。比如这个例子 8,1,9,10,1
dp[0]= 8, 7, 6, 5, 4, 3, 2, 1, 0, (9, 10怎么办？ 填什么值）
☆─────────────────────────────────────☆
hellobruce (大熊蛙 水上漂) 于 (Sun Feb 26 22:29:28 2012, 美东) 提到:
d[i][j] = min { A[i] + d[i-1][j], m[i-1][j] + A[i] - j }
where m[i-1][j] = min of d[i-1][k], for k < j.
感觉还能优化速度。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Sun Feb 26 22:39:26 2012, 美东) 提到:
d[0]怎么定？
如果A［0］＝8， d[9], d[10] 应该填什么值？
☆─────────────────────────────────────☆
hellobruce (大熊蛙 水上漂) 于 (Mon Feb 27 02:52:37 2012, 美东) 提到:
d[0]不用管9和10把。。。等算到9的时候才有..我估计你就是边界条件搞错了。认真考
虑考虑
☆─────────────────────────────────────☆
zhichaow (zhichaow) 于 (Mon Feb 27 10:54:56 2012, 美东) 提到:
用dp实现了一下，内存可以用滚动数组代替变成O(datarange)的空间复杂度，时间复杂
度是O(length*datarange)
public class MinCost {
public int getMin1(int[] input) {
if (input.length <= 1) return 0;
int max = 0;
for (int i = 0; i < input.length; i ++) {
max = Math.max(max, input[i]);
}
int[][] dp = new int[input.length][max+1];
for (int j = 0; j <= max; j ++) {
dp[0][j] = Math.max(0, input[0]-j);
}
for (int i = 1; i < dp.length; i ++) {
for (int j = 0; j <= max; j ++) {
if (input[i] >= j) {
dp[i][j] = input[i]-j+dp[i-1][j];
} else {
dp[i][j] = Math.min(input[i]+dp[i-1][j], dp[i-1][input[i
]]);
}
}
}
return dp[input.length-1][max];
}
public static void main(String args[]) {
int[] in = new int[] {8,1,9,10,1};
int res = new MinCost().getMin1(in);
System.out.println(res);
}
}
☆─────────────────────────────────────☆
louiswang (迷恋音符的疯子) 于 (Mon Feb 27 13:14:23 2012, 美东) 提到:
quick sort，减掉一个数，分成positive negative，两端，然后继续。
☆─────────────────────────────────────☆
Hbase (每天都进步一点点) 于 (Mon Feb 27 13:51:52 2012, 美东) 提到:
这个不对吧， 因为当input[i] < j的时候，没有增加这一个操作锕，只有减少和
eliminate
input[i]不可能会比j小这个情况吧
" dp[i][j] = Math.min(input[i]+dp[i-1][j], dp[i-1][input[i
]]);"
☆─────────────────────────────────────☆
zhichaow (zhichaow) 于 (Mon Feb 27 22:25:44 2012, 美东) 提到:
j是对于每个i是从0开始一直到max的。为什么会没有input[i]
dp[i][j] = Math.min(input[i]+dp[i-1][j], dp[i-1][input[i]]);
这个状态转移是如果input[i]
input[i]+dp[i-1][j]. 另外一种就是保留input[i],那么前i-1个元素都要小于input[i
], cost为dp[i-1][input[i]].
☆─────────────────────────────────────☆
Hbase (每天都进步一点点) 于 (Mon Feb 27 22:38:09 2012, 美东) 提到:
你dp[i,j]的exact定义是什么啊？
[i
☆─────────────────────────────────────☆
zhichaow (zhichaow) 于 (Mon Feb 27 22:44:51 2012, 美东) 提到:
i为当前元素的index，j为第0个元素到第i个元素必须小于的上限。dp[i][j]为使从第0
个元素到第i个元素小于j的最小代价。dp[length][max]即为最终结果。
☆─────────────────────────────────────☆
zhichaow (zhichaow) 于 (Mon Feb 27 22:49:01 2012, 美东) 提到:
i为当前元素的index，j为第0个元素到第i个元素必须小于的上限。dp[i][j]为使从第0
个元素到第i个元素小于j的最小代价。dp[length-1][max]即为最终结果。
其实这个问题就是背包问题的一个变种啊
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Feb 28 01:56:03 2012, 美东) 提到:
请问这步怎么来的：
for (int j = 0; j <= max; j ++) {
dp[0][j] = Math.max(0, input[0]-j);
}
dp[0][j] 不是让input[0] < j的最小cost？
第0
☆─────────────────────────────────────☆
zhichaow (zhichaow) 于 (Tue Feb 28 04:34:49 2012, 美东) 提到:
对的，如果input[0]
cost。
如果input[0]>=j, 那就让input[0]降低到j就可以了，因为这个时候decrease cost总
是小于eliminate的。所以dp[0][j]=input[0]-j就可以了。
综合上面就得出dp[0][j] = Math.max(0, input[0]-j);了
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Feb 28 11:44:05 2012, 美东) 提到:
谢谢，这回看懂了，想错了点东西。
做操作没有 |
|
