logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
牛排的屏不如nexus 7的屏？
avatar
牛排的屏不如nexus 7的屏？# PDA - 掌中宝
B*1
1 楼
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
avatar
k*w
2 楼
即使奥本做的一切都合乎法律，我们也有必要表达我们的不满。NIU能站出来摇旗呐喊
以下，我相信会有很多人响应的。我个人愿意出钱出力，我想和我一样有力使不上的人
还有很多。
avatar
s*r
3 楼
最近买了一只pad用的笔，发现在nexus 7上只用轻轻点就可以了，牛排好像同样的力不
够。但用手指似乎差不多。
不知道这是不是诺基亚批评apple的那个原因之一。
avatar
c*p
4 楼
my 2 cents:
允许额外花费O(n)空间么。。。
允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
当前计数器值放入新开的等大小的数组中。
如果derement的代价是对所有元素为1的话，那cost是O(max(array))；否则是O(sum(ar
ray))

element

【在 B*******1 的大作中提到】
: 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
avatar
c*y
5 楼
参加
avatar
w*c
6 楼
不可能
avatar
g*y
7 楼
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<=jfor (int j=0; jif (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

【在 B*******1 的大作中提到】
: 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
avatar
i*9
8 楼
地点要在奥本上班楼外。
avatar
r*g
9 楼
这个题目没看明白，貌似面试官想让你把排序开销和value大小挂钩。
可以维护一个linkedlist，每次每个元素减少1，一旦有一个元素减少到0，从
linkedlist里面取出插入到list前面，如此反复处理后面的数。
这样总体开销是所有元素的和。
但是，如果你自己直接比较大小，然后交换位置，可能开销更小，也就是说n^2可能比
上面这个算法cost小很多。
所以感觉题目很奇怪，不懂。

ar

【在 c****p 的大作中提到】
: my 2 cents:
: 允许额外花费O(n)空间么。。。
: 允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
: 当前计数器值放入新开的等大小的数组中。
: 如果derement的代价是对所有元素为1的话，那cost是O(max(array))；否则是O(sum(ar
: ray))
:
: element
avatar
w*1
10 楼
同参加

【在 c**y 的大作中提到】
: 参加
avatar
r*g
11 楼
肯定允许
题目要求你只能减少数字，如果不允许，那每个数都被减少的面目全非了，怎么复原？

ar

【在 c****p 的大作中提到】
: my 2 cents:
: 允许额外花费O(n)空间么。。。
: 允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
: 当前计数器值放入新开的等大小的数组中。
: 如果derement的代价是对所有元素为1的话，那cost是O(max(array))；否则是O(sum(ar
: ray))
:
: element
avatar
a*5
12 楼
attend!
avatar
D*I
14 楼
他在哪里上班?
avatar
d*3
15 楼
Try [5,2,2]

【在 g**********y 的大作中提到】
: 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]
: ...
avatar
N*L
16 楼
前面已经回答过一次。游行属于发泄行为，成本高，效果差。性价比不高的事情我们尽
量少做，把有限的资源放到刀刃上。如果有兴趣，请订阅“NIU Action Network”的
Google Group。我们会把未来活动的通知发在那里。

【在 k******w 的大作中提到】
: 即使奥本做的一切都合乎法律，我们也有必要表达我们的不满。NIU能站出来摇旗呐喊
: 以下，我相信会有很多人响应的。我个人愿意出钱出力，我想和我一样有力使不上的人
: 还有很多。
avatar
a*1
17 楼
dp 吧

element

【在 B*******1 的大作中提到】
: 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
avatar
x*7
18 楼
当务之急是把这个抗议的声音传递出去
从美国的社会运作体质来看， 这种行动越公开越好
这种行动怎么会成为“发泄行为” 呢？
为何不能两条腿走路呢？
，

【在 N*********L 的大作中提到】
: 前面已经回答过一次。游行属于发泄行为，成本高，效果差。性价比不高的事情我们尽
: 量少做，把有限的资源放到刀刃上。如果有兴趣，请订阅“NIU Action Network”的
: Google Group。我们会把未来活动的通知发在那里。
avatar
d*3
19 楼

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; jint tmp = (a[i]-h[j]>0)?(a[i]-h[j]):0;
for (int k=i+1; ktmp += dp[j];
if (tmpdp[i] = tmp;
h[i] = (j==n||a[i]}
}
}

cout<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

【在 B*******1 的大作中提到】
: 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
avatar
z*m
20 楼
不发泄出去，别人以为我们很enjoy，很接受现实呢
avatar
l*n
21 楼
你这个怎么也不会是min cost

ar

【在 c****p 的大作中提到】
: my 2 cents:
: 允许额外花费O(n)空间么。。。
: 允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
: 当前计数器值放入新开的等大小的数组中。
: 如果derement的代价是对所有元素为1的话，那cost是O(max(array))；否则是O(sum(ar
: ray))
:
: element
avatar
b*8
22 楼
游行不管是不是发泄，其实都是最有效的方式，怎么就不能考虑呢？实在有些不能理解
。会叫的才有奶吃，在老美这里就只能这样
avatar
l*n
23 楼
有没有insert？

element

【在 B*******1 的大作中提到】
: 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
avatar
r*g
24 楼
这个题目到底什么意思啊，题目说only valid operation，就是说那些简单的比较，需
要的cost都是和数字大小有关，比如说if(ai>aj)，是不是不能直接比较，如果不能的
话，需要的cost是不是abs(ai-aj)，所以他要求的cost根本不是传统意义上的n^2, n^3
之类的啊。
要降低cost，就要降低比较的次数，这样对所有元素一起decrement到其中一个为0貌似
最好。
其他任何办法，不管怎么比较，至少O(nlogn)，但是每次比较都意味着O(ai)的开销，
那岂不是肯定开销很大？

element

【在 B*******1 的大作中提到】
: 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
avatar
r*g
25 楼
为何不是，题目的only valid operation是什么意思？

【在 l******n 的大作中提到】
: 你这个怎么也不会是min cost
:
: ar
avatar
h*6
26 楼
dp题，前n项以x结尾所需最小消耗为dp[n][x]
总复杂度为O(n*datarange^2)
avatar
r*g
27 楼
能够详细讲讲思路？

【在 h**6 的大作中提到】
: dp题，前n项以x结尾所需最小消耗为dp[n][x]
: 总复杂度为O(n*datarange^2)
avatar
B*1
28 楼
恍然大悟，就是这个dp了。

【在 h**6 的大作中提到】
: dp题，前n项以x结尾所需最小消耗为dp[n][x]
: 总复杂度为O(n*datarange^2)
avatar
r*g
29 楼
看不懂
先问个简单问题，两个很大的数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岂不是。。。。没有讨论的必要了。

【在 B*******1 的大作中提到】
: 恍然大悟，就是这个dp了。
avatar
x*s
30 楼
我的理解：
1.比较不算在cost里面，只有改变数组的操作算cost
2. 另外得到的数组应该不是原数组的排序。 对数组[10000， 9999] cost是1，只需要
把10000减1就得到9999,9999。
无法sort原数组，因为不可以增加任何元素的值。 无论是减少元素值还是移除元素，
都有cost，cost的值就是这个元素少掉的值，可以理解为为了达到递增的损耗。
3. 对每个元素，要决定是要除掉他还是减低一部分值。最后总的cost就是原数组的和
与得到数组的和的差值。 目的是使得这个差值最小，可以理解为损耗最小吧。

【在 r*******g 的大作中提到】
: 看不懂
: 先问个简单问题，两个很大的数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岂不是。。。。没有讨论的必要了。
avatar
n*d
31 楼
牛人好多。。

element

【在 B*******1 的大作中提到】
: 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
avatar
t*n
32 楼
try {5,3,5,3,2}

{

【在 d****3 的大作中提到】
:
: 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;
avatar
d*3
33 楼
Thanks for pointing out my error!
From your instance, I could see that my algorithm is completely wrong.
Need to rethink...

【在 t*****n 的大作中提到】
: try {5,3,5,3,2}
:
: {
avatar
q*x
34 楼
npc possible?

element

【在 B*******1 的大作中提到】
: 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
avatar
r*g
35 楼
http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-valu
我大概理解你的意思了，如果比较没有cost，而且无法直接sort数组，那么只能依次把
一个数删除掉这样来排序。

【在 x******s 的大作中提到】
: 我的理解：
: 1.比较不算在cost里面，只有改变数组的操作算cost
: 2. 另外得到的数组应该不是原数组的排序。 对数组[10000， 9999] cost是1，只需要
: 把10000减1就得到9999,9999。
: 无法sort原数组，因为不可以增加任何元素的值。 无论是减少元素值还是移除元素，
: 都有cost，cost的值就是这个元素少掉的值，可以理解为为了达到递增的损耗。
: 3. 对每个元素，要决定是要除掉他还是减低一部分值。最后总的cost就是原数组的和
: 与得到数组的和的差值。 目的是使得这个差值最小，可以理解为损耗最小吧。
avatar
B*1
36 楼
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
avatar
c*p
37 楼
my 2 cents:
允许额外花费O(n)空间么。。。
允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
当前计数器值放入新开的等大小的数组中。
如果derement的代价是对所有元素为1的话，那cost是O(max(array))；否则是O(sum(ar
ray))

element

【在 B*******1 的大作中提到】
: 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
avatar
g*y
38 楼
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<=jfor (int j=0; jif (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

【在 B*******1 的大作中提到】
: 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
avatar
r*g
39 楼
这个题目没看明白，貌似面试官想让你把排序开销和value大小挂钩。
可以维护一个linkedlist，每次每个元素减少1，一旦有一个元素减少到0，从
linkedlist里面取出插入到list前面，如此反复处理后面的数。
这样总体开销是所有元素的和。
但是，如果你自己直接比较大小，然后交换位置，可能开销更小，也就是说n^2可能比
上面这个算法cost小很多。
所以感觉题目很奇怪，不懂。

ar

【在 c****p 的大作中提到】
: my 2 cents:
: 允许额外花费O(n)空间么。。。
: 允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
: 当前计数器值放入新开的等大小的数组中。
: 如果derement的代价是对所有元素为1的话，那cost是O(max(array))；否则是O(sum(ar
: ray))
:
: element
avatar
r*g
40 楼
肯定允许
题目要求你只能减少数字，如果不允许，那每个数都被减少的面目全非了，怎么复原？

ar

【在 c****p 的大作中提到】
: my 2 cents:
: 允许额外花费O(n)空间么。。。
: 允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
: 当前计数器值放入新开的等大小的数组中。
: 如果derement的代价是对所有元素为1的话，那cost是O(max(array))；否则是O(sum(ar
: ray))
:
: element
avatar
d*3
42 楼
Try [5,2,2]

【在 g**********y 的大作中提到】
: 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]
: ...
avatar
a*1
43 楼
dp 吧

element

【在 B*******1 的大作中提到】
: 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
avatar
d*3
44 楼

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; jint tmp = (a[i]-h[j]>0)?(a[i]-h[j]):0;
for (int k=i+1; ktmp += dp[j];
if (tmpdp[i] = tmp;
h[i] = (j==n||a[i]}
}
}

cout<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

【在 B*******1 的大作中提到】
: 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
avatar
l*n
45 楼
你这个怎么也不会是min cost

ar

【在 c****p 的大作中提到】
: my 2 cents:
: 允许额外花费O(n)空间么。。。
: 允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
: 当前计数器值放入新开的等大小的数组中。
: 如果derement的代价是对所有元素为1的话，那cost是O(max(array))；否则是O(sum(ar
: ray))
:
: element
avatar
l*n
46 楼
有没有insert？

element

【在 B*******1 的大作中提到】
: 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
avatar
r*g
47 楼
这个题目到底什么意思啊，题目说only valid operation，就是说那些简单的比较，需
要的cost都是和数字大小有关，比如说if(ai>aj)，是不是不能直接比较，如果不能的
话，需要的cost是不是abs(ai-aj)，所以他要求的cost根本不是传统意义上的n^2, n^3
之类的啊。
要降低cost，就要降低比较的次数，这样对所有元素一起decrement到其中一个为0貌似
最好。
其他任何办法，不管怎么比较，至少O(nlogn)，但是每次比较都意味着O(ai)的开销，
那岂不是肯定开销很大？

element

【在 B*******1 的大作中提到】
: 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
avatar
r*g
48 楼
为何不是，题目的only valid operation是什么意思？

【在 l******n 的大作中提到】
: 你这个怎么也不会是min cost
:
: ar
avatar
h*6
49 楼
dp题，前n项以x结尾所需最小消耗为dp[n][x]
总复杂度为O(n*datarange^2)
avatar
r*g
50 楼
能够详细讲讲思路？

【在 h**6 的大作中提到】
: dp题，前n项以x结尾所需最小消耗为dp[n][x]
: 总复杂度为O(n*datarange^2)
avatar
B*1
51 楼
恍然大悟，就是这个dp了。

【在 h**6 的大作中提到】
: dp题，前n项以x结尾所需最小消耗为dp[n][x]
: 总复杂度为O(n*datarange^2)
avatar
r*g
52 楼
看不懂
先问个简单问题，两个很大的数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岂不是。。。。没有讨论的必要了。

【在 B*******1 的大作中提到】
: 恍然大悟，就是这个dp了。
avatar
x*s
53 楼
我的理解：
1.比较不算在cost里面，只有改变数组的操作算cost
2. 另外得到的数组应该不是原数组的排序。 对数组[10000， 9999] cost是1，只需要
把10000减1就得到9999,9999。
无法sort原数组，因为不可以增加任何元素的值。 无论是减少元素值还是移除元素，
都有cost，cost的值就是这个元素少掉的值，可以理解为为了达到递增的损耗。
3. 对每个元素，要决定是要除掉他还是减低一部分值。最后总的cost就是原数组的和
与得到数组的和的差值。 目的是使得这个差值最小，可以理解为损耗最小吧。

【在 r*******g 的大作中提到】
: 看不懂
: 先问个简单问题，两个很大的数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岂不是。。。。没有讨论的必要了。
avatar
n*d
54 楼
牛人好多。。

element

【在 B*******1 的大作中提到】
: 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
avatar
t*n
55 楼
try {5,3,5,3,2}

{

【在 d****3 的大作中提到】
:
: 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;
avatar
d*3
56 楼
Thanks for pointing out my error!
From your instance, I could see that my algorithm is completely wrong.
Need to rethink...

【在 t*****n 的大作中提到】
: try {5,3,5,3,2}
:
: {
avatar
q*x
57 楼
npc possible?

element

【在 B*******1 的大作中提到】
: 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
avatar
r*g
58 楼
http://shashank7s.blogspot.com/2011/05/wap-to-find-minimum-valu
我大概理解你的意思了，如果比较没有cost，而且无法直接sort数组，那么只能依次把
一个数删除掉这样来排序。

【在 x******s 的大作中提到】
: 我的理解：
: 1.比较不算在cost里面，只有改变数组的操作算cost
: 2. 另外得到的数组应该不是原数组的排序。 对数组[10000， 9999] cost是1，只需要
: 把10000减1就得到9999,9999。
: 无法sort原数组，因为不可以增加任何元素的值。 无论是减少元素值还是移除元素，
: 都有cost，cost的值就是这个元素少掉的值，可以理解为为了达到递增的损耗。
: 3. 对每个元素，要决定是要除掉他还是减低一部分值。最后总的cost就是原数组的和
: 与得到数组的和的差值。 目的是使得这个差值最小，可以理解为损耗最小吧。
avatar
S*Y
59 楼
怎么个恍然大悟法？ 能不能解释下？

【在 B*******1 的大作中提到】
: 恍然大悟，就是这个dp了。
avatar
p*2
60 楼

昨天想了想，没想太明白。DP还是太弱了。

【在 S**Y 的大作中提到】
: 怎么个恍然大悟法？ 能不能解释下？
avatar
h*e
61 楼
very basic undergraduate dp problem.
avatar
H*e
62 楼
晕
说下思路？

【在 h********e 的大作中提到】
: very basic undergraduate dp problem.
avatar
y*n
63 楼
同意这个。
"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

【在 x******s 的大作中提到】
: 我的理解：
: 1.比较不算在cost里面，只有改变数组的操作算cost
: 2. 另外得到的数组应该不是原数组的排序。 对数组[10000， 9999] cost是1，只需要
: 把10000减1就得到9999,9999。
: 无法sort原数组，因为不可以增加任何元素的值。 无论是减少元素值还是移除元素，
: 都有cost，cost的值就是这个元素少掉的值，可以理解为为了达到递增的损耗。
: 3. 对每个元素，要决定是要除掉他还是减低一部分值。最后总的cost就是原数组的和
: 与得到数组的和的差值。 目的是使得这个差值最小，可以理解为损耗最小吧。
avatar
h*e
64 楼
看了一下回帖，han6 的算法是对的。但是多了一维。 可以n*datarange做完。计算的
时候可以优化。
d[i][j] 存的是前i个，最后一个最高是j的时候的最优费用。 可以从d[i-1][*]算出来
。整个d[i][*]应该可以从d[i-1][*]用datarange时间算出来。
avatar
p*2
65 楼

能给个例子吗？我昨天按照这个思路做了做，不能做对。

【在 h********e 的大作中提到】
: 看了一下回帖，han6 的算法是对的。但是多了一维。 可以n*datarange做完。计算的
: 时候可以优化。
: d[i][j] 存的是前i个，最后一个最高是j的时候的最优费用。 可以从d[i-1][*]算出来
: 。整个d[i][*]应该可以从d[i-1][*]用datarange时间算出来。
avatar
h*e
66 楼
你把程序贴一下。。。例子太麻烦了
avatar
p*2
67 楼

总是发现有地方不对，改了之后，其他地方又不对。比如这个例子 8,1,9,10,1
dp[0]= 8, 7, 6, 5, 4, 3, 2, 1, 0, (9, 10怎么办？ 填什么值）

【在 h********e 的大作中提到】
: 你把程序贴一下。。。例子太麻烦了
avatar
h*e
68 楼
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.
感觉还能优化速度。
avatar
p*2
69 楼

d[0]怎么定？
如果A［0］＝8， d[9], d[10] 应该填什么值？

【在 h********e 的大作中提到】
: 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.
: 感觉还能优化速度。
avatar
h*e
70 楼
d[0]不用管9和10把。。。等算到9的时候才有..我估计你就是边界条件搞错了。认真考
虑考虑
avatar
z*w
71 楼
用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);
}
}
avatar
l*g
72 楼
quick sort，减掉一个数，分成positive negative，两端，然后继续。

【在 r*******g 的大作中提到】
: 能够详细讲讲思路？
avatar
H*e
73 楼
这个不对吧， 因为当input[i] < j的时候，没有增加这一个操作锕，只有减少和
eliminate
input[i]不可能会比j小这个情况吧
" dp[i][j] = Math.min(input[i]+dp[i-1][j], dp[i-1][input[i
]]);"

【在 z******w 的大作中提到】
: 用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]);
: }
avatar
z*w
74 楼
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]].

【在 H***e 的大作中提到】
: 这个不对吧， 因为当input[i] < j的时候，没有增加这一个操作锕，只有减少和
: eliminate
: input[i]不可能会比j小这个情况吧
: " dp[i][j] = Math.min(input[i]+dp[i-1][j], dp[i-1][input[i
: ]]);"
avatar
H*e
75 楼
你dp[i,j]的exact定义是什么啊？

[i

【在 z******w 的大作中提到】
: 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]].
avatar
z*w
76 楼
i为当前元素的index，j为第0个元素到第i个元素必须小于的上限。dp[i][j]为使从第0
个元素到第i个元素小于j的最小代价。dp[length][max]即为最终结果。
avatar
z*w
77 楼
i为当前元素的index，j为第0个元素到第i个元素必须小于的上限。dp[i][j]为使从第0
个元素到第i个元素小于j的最小代价。dp[length-1][max]即为最终结果。
其实这个问题就是背包问题的一个变种啊

【在 H***e 的大作中提到】
: 你dp[i,j]的exact定义是什么啊？
:
: [i
avatar
B*1
78 楼
请问这步怎么来的：
for (int j = 0; j <= max; j ++) {
dp[0][j] = Math.max(0, input[0]-j);
}
dp[0][j] 不是让input[0] < j的最小cost？

第0

【在 z******w 的大作中提到】
: i为当前元素的index，j为第0个元素到第i个元素必须小于的上限。dp[i][j]为使从第0
: 个元素到第i个元素小于j的最小代价。dp[length-1][max]即为最终结果。
: 其实这个问题就是背包问题的一个变种啊
avatar
z*w
79 楼
对的，如果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);了

【在 B*******1 的大作中提到】
: 请问这步怎么来的：
: for (int j = 0; j <= max; j ++) {
: dp[0][j] = Math.max(0, input[0]-j);
: }
: dp[0][j] 不是让input[0] < j的最小cost？
:
: 第0
avatar
B*1
80 楼
谢谢，这回看懂了，想错了点东西。

做操作没有

【在 z******w 的大作中提到】
: 对的，如果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);了
相关阅读
从来不在乎手机电池的应该都是宅男联想 5.5寸平板 K900似乎不错的样子如果Nokia跟Google合作...lenovo outlet有thinkpad tablet 一代 32G $189有用motolora razr 的么？LG Optimus L9 有没有短信提醒功能？家里还有个HP TP的无线充电器，在家搞了个apache 然后所有视屏都变成mp4格式google music自己可以加cover art？请问Dell的这个设计是不是现在独有的？nexus 7连不上wifi怎么回事我的电池ZDNet Win8失败的5个原因你们看iWatch会是个啥样的？从NT版本号来看，win8的地位连vista和2000都不如win8 hyperV 能否在两个系统间自由切换ChromeOS为什么不做成Web desktoptmobile对某些电话发中文短信会出现乱码海美迪 netflix的问题估计HTC One 3月底钱前上不了市了吧
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。