z**********g
发帖数: 209 | 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
没想清楚。 |
l*********8
发帖数: 4642 | |
l******c
发帖数: 2555 | 3 if there is no compare op, how to know it is sorted?
element
【在 z**********g 的大作中提到】
: 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
: 没想清楚。
|
c****p
发帖数: 6474 | 4 有比较吧。
【在 l******c 的大作中提到】
: if there is no compare op, how to know it is sorted?
:
: element
|
z**********g
发帖数: 209 | 5 能讲讲吗.谢谢！
【在 l*********8 的大作中提到】
: 想到一个O(n^2)解法，再想想。。。
|
h****e
发帖数: 928 | |
z**********g
发帖数: 209 | 7 O(N^2) 对我来说很好了，但是careercup 的讨论太多了，请问谁的是对的。 |
h****e
发帖数: 928 | 8 请问1log1+2log2+...+NlogN的复杂度是多少？是N*NlogN，还是
N*N。 |
o******y
发帖数: 446 | 9 1log1+2log2+...+NlogN > N/2*logN/2 + .... + NlogN > N/2 * N/2 * log N/2
1log1+2log2+...+NlogN < N*NlogN
而 N/2 * N/2 * log N/2 与 N*NlogN 无本质区别。 所以是 N*NlogN
【在 h****e 的大作中提到】
: 请问1log1+2log2+...+NlogN的复杂度是多少？是N*NlogN，还是
: N*N。
|
h****e
发帖数: 928 | 10 多谢。看来我的解法是N*NlogN的，还是不行。:(
【在 o******y 的大作中提到】
: 1log1+2log2+...+NlogN > N/2*logN/2 + .... + NlogN > N/2 * N/2 * log N/2
: 1log1+2log2+...+NlogN < N*NlogN
: 而 N/2 * N/2 * log N/2 与 N*NlogN 无本质区别。 所以是 N*NlogN
|
|
|
h****e
发帖数: 928 | 11 我想如下greedy解法应该是N*N的吧：
从头开始，A[1]到A[K]已经是排好序的。下面看A[K+1]:
有两种可能：
一是删除A[K+1]，cost是A[K+1]
二是用二分法找A[1..K]中大于A[K+1]的数，假设是A[M]，
那么把A[M]到A[K]中的数减小到A[K+1]，cost是
(A[M]-A[K+1]) + ... + (A[K]-A[K+1])
取以上最小的cost，再继续往后遍历直到N为止。
这样复杂度是(log1+1/2)+(log2+2/2)+...(logK+K/2)+...+(logN+N/2) = N*N。
这样做对吗？还有更高效的解法吗？ |
b****e
发帖数: 45 | 12 想到一个O(n^2)的greedy算法，大概思路如下：
Traverse from the last element back to the first element. For each
element a[i]:
(1) If a[i] <= a[i + 1], then continue;
(2) If a[i] > a[i + 1], then compare the cost of decreasing the
current element a[i] with the cost of deleting the elements
a[i+1]...a[j], where (i+1)<= j < n. Choose either the decrement
or deletion operation that incurs the minimum cost.
以下是程序代码：
void MakeSortedArray(int arr[], int n) {
if (n <= 1)
return;
for (int i = n - 2; i >=0; i--) {
if (arr[i] <= arr[i + 1])
continue;
// initial deletion cost
int del_cost = 0;
// initial deletion position
int del_pos = i + 1;
// initial minimum cost is the decrement cost
int min_cost = arr[i] - arr[i + 1];
for (int j = i + 1; j < n; j++) {
// deleted elements are marked as -1
if (arr[j] < 0)
continue;
// new decrement cost
int new_dec_cost = (arr[i] > arr[j]) ?
(arr[i] - arr[j]) : 0;
int new_cost = new_dec_cost + del_cost;
if (new_cost < min_cost) {
min_cost = new_cost;
del_pos = j;
}
del_cost += arr[j];
}
arr[i] = arr[del_pos];
// mark all the elements in the middle as deleted
for (int k = i + 1; k < del_pos; k++)
arr[k] = -1;
}
}
with
element
【在 z**********g 的大作中提到】
: 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
: 没想清楚。
|
z**********g
发帖数: 209 | 13 谢谢代码！ 我看一下...
【在 b****e 的大作中提到】
: 想到一个O(n^2)的greedy算法，大概思路如下：
: Traverse from the last element back to the first element. For each
: element a[i]:
: (1) If a[i] <= a[i + 1], then continue;
: (2) If a[i] > a[i + 1], then compare the cost of decreasing the
: current element a[i] with the cost of deleting the elements
: a[i+1]...a[j], where (i+1)<= j < n. Choose either the decrement
: or deletion operation that incurs the minimum cost.
:
: 以下是程序代码：
|
b****e
发帖数: 45 | 14 从左往右的算法有个问题是无法考虑到后续元素对当前元素操作的影响，比如以下数组：
{3, 5, 6, 3, 3}
按照你的这个算法，最后两个元素都会被删掉，但其累计的cost比减少中间两个元素更
大。
【在 h****e 的大作中提到】
: 我想如下greedy解法应该是N*N的吧：
: 从头开始，A[1]到A[K]已经是排好序的。下面看A[K+1]:
: 有两种可能：
: 一是删除A[K+1]，cost是A[K+1]
: 二是用二分法找A[1..K]中大于A[K+1]的数，假设是A[M]，
: 那么把A[M]到A[K]中的数减小到A[K+1]，cost是
: (A[M]-A[K+1]) + ... + (A[K]-A[K+1])
: 取以上最小的cost，再继续往后遍历直到N为止。
: 这样复杂度是(log1+1/2)+(log2+2/2)+...(logK+K/2)+...+(logN+N/2) = N*N。
: 这样做对吗？还有更高效的解法吗？
|
h****e
发帖数: 928 | 15 明白了，多谢指正。
组：
【在 b****e 的大作中提到】
: 从左往右的算法有个问题是无法考虑到后续元素对当前元素操作的影响，比如以下数组：
: {3, 5, 6, 3, 3}
: 按照你的这个算法，最后两个元素都会被删掉，但其累计的cost比减少中间两个元素更
: 大。
|
n****o
发帖数: 399 | 16 4 1 2 3好像不对
【在 h****e 的大作中提到】
: 我想如下greedy解法应该是N*N的吧：
: 从头开始，A[1]到A[K]已经是排好序的。下面看A[K+1]:
: 有两种可能：
: 一是删除A[K+1]，cost是A[K+1]
: 二是用二分法找A[1..K]中大于A[K+1]的数，假设是A[M]，
: 那么把A[M]到A[K]中的数减小到A[K+1]，cost是
: (A[M]-A[K+1]) + ... + (A[K]-A[K+1])
: 取以上最小的cost，再继续往后遍历直到N为止。
: 这样复杂度是(log1+1/2)+(log2+2/2)+...(logK+K/2)+...+(logN+N/2) = N*N。
: 这样做对吗？还有更高效的解法吗？
|
n****o
发帖数: 399 | 17 从左往右和从有往左的本质区别是什么呢？
组：
【在 b****e 的大作中提到】
: 从左往右的算法有个问题是无法考虑到后续元素对当前元素操作的影响，比如以下数组：
: {3, 5, 6, 3, 3}
: 按照你的这个算法，最后两个元素都会被删掉，但其累计的cost比减少中间两个元素更
: 大。
|
h****e
发帖数: 928 | 18 好象从右往左也不对，例如:
5 5 5 6 3 3
从左往右得到的Cost是6(删除最后两个3)：5 5 5 6
从右往左得到的Cost是9: 3 3 3 3 3 3 |
c****p
发帖数: 6474 | 19 这题版上以前讨论过。我当时还把题意理解错了。
【在 h****e 的大作中提到】
: 好象从右往左也不对，例如:
: 5 5 5 6 3 3
: 从左往右得到的Cost是6(删除最后两个3)：5 5 5 6
: 从右往左得到的Cost是9: 3 3 3 3 3 3
|
b****e
发帖数: 45 | 20 我的理解是这样：按照从小到大排序的话，decrement应该是基于跟后续元素的比较所
作出的操作，而不是跟前面元素比较得出的操作。因此从右往左移的话，对当前元素的
decrement操作能够保证对所有后续元素的有效性。这一有效性是实现上面的greedy算
法中每一步cost函数有效性的基础。而如果从左往右的话，对当前元素的decrement操
作无法保证其对后续元素的一致有效性，所以由此而得出的cost函数也是无效的。
如果题目变成只允许increment和deletion操作，则应该从左往右判断。
大概就是这个样子，可能解释得不太清楚 :-)
【在 n****o 的大作中提到】
: 从左往右和从有往左的本质区别是什么呢？
:
: 组：
|
|
|
n****o
发帖数: 399 | 21
如果允许increment和deletion，从左往右也不对啊，比如 4 1 2 3
主要是你那个从右往左的方法好像不容易找到反例，但是也不容易想清楚greedy方法一
定能得到最优的解
【在 b****e 的大作中提到】
: 我的理解是这样：按照从小到大排序的话，decrement应该是基于跟后续元素的比较所
: 作出的操作，而不是跟前面元素比较得出的操作。因此从右往左移的话，对当前元素的
: decrement操作能够保证对所有后续元素的有效性。这一有效性是实现上面的greedy算
: 法中每一步cost函数有效性的基础。而如果从左往右的话，对当前元素的decrement操
: 作无法保证其对后续元素的一致有效性，所以由此而得出的cost函数也是无效的。
: 如果题目变成只允许increment和deletion操作，则应该从左往右判断。
: 大概就是这个样子，可能解释得不太清楚 :-)
|
l******i
发帖数: 103 | 22 用dp，cost[i,j]记录将a[0...i]变成最后一个元素不大于j的sorted array所需要的最
小cost。求cost[i+1,j]时，考察包含a[i+1]（a[0...i+1]都变成不大于j）和不包含a[
i+1](去掉a[i+1]，将a[0...i]变成不大于j的数）两种情况下的cost，取较小值。。代
码如下，大家帮忙看看有没有错。思路和代码。
int minimum_cost(vector &v) {
if (v.size() <= 1) return 0;
int n = v.size();
map cost;
vector sorted(v);
sort(sorted.begin(), sorted.end());
vector::iterator it = unique(sorted.begin(), sorted.end());
sorted.resize(it-sorted.begin());
int newlen = sorted.size();
for (int j = 0; j < newlen; j ++) {
cost[sorted[j]] = (sorted[j] >= v[0] ? 0 : v[0] - sorted[j]);
}
for (int i = 1; i < n; i ++) {
int rev = cost[v[i]];
for (int j = newlen-1; j >= 0; j --) {
int with = rev;
if (sorted[j] < v[i])
with = cost[sorted[j]] + v[i] - sorted[j];
int without = cost[sorted[j]] + v[i];
cost[sorted[j]] = min(with, without);
}
}
int res = INT_MAX;
for (map::iterator iter = cost.begin(); iter !=
cost.end(); iter ++) {
res = min(res, iter->second);
}
return res;
} |
b****e
发帖数: 45 | 23 多谢你的反例！我的解法确实也有问题。
看来不管从左往右还是从右往左都没办法完全考虑到达成全局最优的条件，
Greedy算法可能行不通。
【在 h****e 的大作中提到】
: 好象从右往左也不对，例如:
: 5 5 5 6 3 3
: 从左往右得到的Cost是6(删除最后两个3)：5 5 5 6
: 从右往左得到的Cost是9: 3 3 3 3 3 3
|
b****e
发帖数: 45 | 24 感觉你的DP思路应该是对的，这样能够保证每次比较cost时的全局判断。
a[
【在 l******i 的大作中提到】
: 用dp，cost[i,j]记录将a[0...i]变成最后一个元素不大于j的sorted array所需要的最
: 小cost。求cost[i+1,j]时，考察包含a[i+1]（a[0...i+1]都变成不大于j）和不包含a[
: i+1](去掉a[i+1]，将a[0...i]变成不大于j的数）两种情况下的cost，取较小值。。代
: 码如下，大家帮忙看看有没有错。思路和代码。
: int minimum_cost(vector &v) {
: if (v.size() <= 1) return 0;
: int n = v.size();
: map cost;
: vector sorted(v);
: sort(sorted.begin(), sorted.end());
|
l*********8
发帖数: 4642 | 25 Your program is correct, I think.
a[
【在 l******i 的大作中提到】
: 用dp，cost[i,j]记录将a[0...i]变成最后一个元素不大于j的sorted array所需要的最
: 小cost。求cost[i+1,j]时，考察包含a[i+1]（a[0...i+1]都变成不大于j）和不包含a[
: i+1](去掉a[i+1]，将a[0...i]变成不大于j的数）两种情况下的cost，取较小值。。代
: 码如下，大家帮忙看看有没有错。思路和代码。
: int minimum_cost(vector &v) {
: if (v.size() <= 1) return 0;
: int n = v.size();
: map cost;
: vector sorted(v);
: sort(sorted.begin(), sorted.end());
|
S*******e
发帖数: 379 | 26 这题我题目我怎么没看懂呢。
是说新生成的array不需要保存原来的值吗？只要是sorted的就行？
另外如果delete了一个element后，是不是不可能再给那个element赋值了？
element
【在 z**********g 的大作中提到】
: 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
: 没想清楚。
|
S*******e
发帖数: 379 | 27 这个很牛，不过好像assume了可以把数组中间的元素删除？
还是我理解错了？
a[
【在 l******i 的大作中提到】
: 用dp，cost[i,j]记录将a[0...i]变成最后一个元素不大于j的sorted array所需要的最
: 小cost。求cost[i+1,j]时，考察包含a[i+1]（a[0...i+1]都变成不大于j）和不包含a[
: i+1](去掉a[i+1]，将a[0...i]变成不大于j的数）两种情况下的cost，取较小值。。代
: 码如下，大家帮忙看看有没有错。思路和代码。
: int minimum_cost(vector &v) {
: if (v.size() <= 1) return 0;
: int n = v.size();
: map cost;
: vector sorted(v);
: sort(sorted.begin(), sorted.end());
|
H****r
发帖数: 2801 | 28 完了，根本看不懂题意... 能来个例子不？
element
【在 z**********g 的大作中提到】
: 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
: 没想清楚。
|
r********g
发帖数: 1351 | 29 数组四个元素：5,6,3,3
最佳解法是：把5减成3，cost是2次decrements,把6减成3，cost是3次decrements，这
样得到的结果是：3,3,3,3 total cost是5
另外一个解法是：把最后2个3删掉，cost是3+3=6，这个就不是最优解法。
楼上的DP是正解。。。膜拜中。。
【在 H****r 的大作中提到】
: 完了，根本看不懂题意... 能来个例子不？
:
: element
|
s******k
发帖数: 3716 | 30 不是把６变成４？
【在 r********g 的大作中提到】
: 数组四个元素：5,6,3,3
: 最佳解法是：把5减成3，cost是2次decrements,把6减成3，cost是3次decrements，这
: 样得到的结果是：3,3,3,3 total cost是5
: 另外一个解法是：把最后2个3删掉，cost是3+3=6，这个就不是最优解法。
: 楼上的DP是正解。。。膜拜中。。
|
|
|
s********0
发帖数: 34 | 31 题目如果稍微改下条件：要求“严格”递增
上面的j就不能单单考虑数组中的数了 按照上面的dp我试着改写了下
ms还是有些问题 求neat的解答 |
