s****t
发帖数: 36 | 1 在careercup上面看的，题目看不是很懂，大家看看是问什么东西啊。
Given n elements, sort the elements. Here, only one operation is
permitted decreaseValue..
Note that you cannot swap the values.. output should be a sorted
list..
if input is 4 5 2 1 3
output is 3 3 3.. There can be many answers.. Give the optimum
solution with minimum cost. where as cost is the sum of decreased
amounts..
for this example, 4,5 are decreased by 1.. 2 is decreased by 2.. 1
is decreased by 1.. |
m*****g
发帖数: 226 | |
s*******s
发帖数: 46 | 3 4 5 2 1 3 -> 3 3 3 the sum of decreased value is 6
4 5 2 1 3 -> 4 3 2 1 the sum of decreased value is 5
get confused?
Do I misunderstand the question? |
b***u
发帖数: 61 | 4
为啥少了两个数呢？2 和1去哪里了？
【在 s*******s 的大作中提到】
: 4 5 2 1 3 -> 3 3 3 the sum of decreased value is 6
: 4 5 2 1 3 -> 4 3 2 1 the sum of decreased value is 5
: get confused?
: Do I misunderstand the question?
|
B*****t
发帖数: 335 | 5 I think O(n^2) is already the optimal solution.
【在 m*****g 的大作中提到】
: 只能想到n*n的解法
|
m*****g
发帖数: 226 | 6 4 5 2 1 3 -> 3 3 3
你那个变成倒序了
【在 s*******s 的大作中提到】
: 4 5 2 1 3 -> 3 3 3 the sum of decreased value is 6
: 4 5 2 1 3 -> 4 3 2 1 the sum of decreased value is 5
: get confused?
: Do I misunderstand the question?
|
m*****g
发帖数: 226 | 7 and it is a brutal force one.
【在 B*****t 的大作中提到】
: I think O(n^2) is already the optimal solution.
|
B*****t
发帖数: 335 | 8 so could you please present your O(N^2) approach?
【在 m*****g 的大作中提到】
: and it is a brutal force one.
|
m*****g
发帖数: 226 | 9 input array array[1...n]
for int i from 1 to n
calculate the decreases needed if the output max is array[i]
that is it.
【在 B*****t 的大作中提到】
: so could you please present your O(N^2) approach?
|
B*****t
发帖数: 335 | 10 the problem is how to calculate the decreases needed if the output
max is array[i]
【在 m*****g 的大作中提到】
: input array array[1...n]
: for int i from 1 to n
: calculate the decreases needed if the output max is array[i]
: that is it.
|
|
|
m*****g
发帖数: 226 | 11 input array 5 4 3 2 1
5: 5 (rest all reduced to none, so add them up as u visit them)
4: 4 4 (get the first diff, add the rest up)
3: 3 3 3
2: 2 2 2 2
1: 1 1 1 1 1
每个只要算一遍就行了吧，不至于真的要一个一个减吧
【在 B*****t 的大作中提到】
: the problem is how to calculate the decreases needed if the output
: max is array[i]
|
B*****t
发帖数: 335 | 12 what about 4 8 6 3 5 7 ?? how do you calculate min decreased
value?
【在 m*****g 的大作中提到】
: input array 5 4 3 2 1
: 5: 5 (rest all reduced to none, so add them up as u visit them)
: 4: 4 4 (get the first diff, add the rest up)
: 3: 3 3 3
: 2: 2 2 2 2
: 1: 1 1 1 1 1
: 每个只要算一遍就行了吧，不至于真的要一个一个减吧
|
m*****g
发帖数: 226 | 13 全都找一遍阿，不然干什么要O(n2)。都找一遍了看谁最小阿
4：4 4 (-3) 4 (-2) 0(-3) 4(-1) 4 (-3)
【在 B*****t 的大作中提到】
: what about 4 8 6 3 5 7 ?? how do you calculate min decreased
: value?
|
m*****g
发帖数: 226 | 14 又想了一下，这个方法行不通。
等高手了
【在 m*****g 的大作中提到】
: 全都找一遍阿，不然干什么要O(n2)。都找一遍了看谁最小阿
: 4：4 4 (-3) 4 (-2) 0(-3) 4(-1) 4 (-3)
|
B*****t
发帖数: 335 | 15 I think either you or me misunderstand the problem.
sort the elements does not need to make them all equal
【在 m*****g 的大作中提到】
: 全都找一遍阿，不然干什么要O(n2)。都找一遍了看谁最小阿
: 4：4 4 (-3) 4 (-2) 0(-3) 4(-1) 4 (-3)
|
m*****g
发帖数: 226 | 16 what is wrong is my solution. i think i get the problem right.
【在 B*****t 的大作中提到】
: I think either you or me misunderstand the problem.
: sort the elements does not need to make them all equal
|
K******g
发帖数: 1870 | 17 请问谁能把这个问题解释一遍？我看了大半天，不知所云。 |
h**k
发帖数: 3368 | 18 我的理解是，输入无序数组，不能交换数组位置，只能减少数组中的元素值；如果某个
元素减为零，则认为从数组中移走。输出一个排序的数组，要求减少量最小。
怀疑是NP-hard问题，可以用穷举法找到最优解；用greedy算法给出近似解。
DP似乎不行。 |
