This is a nice problem. It looks like a trivial matroid, so a greedy
algorithm will work fine. The obvious greedy algorithm is to work
left-to-right and incorporate elements into the sorted order one-by-
one. In each case, you have 2 choices. The first is to decrement
elements to the left by the amount needed to restore non-decreasing
order. The second is to delete the new element. The cost of each is
easy to calculate. Pick the choice with least cost and continue.
This algorithm is O(n^2). There may be a faster way to do it, but I
can't see one.
#include <stdio.h>
int make_nondecreasing(int *a, int n)
{
int i, j, dec, dec_cost, total_cost;
total_cost = 0;
for (i = 0; i < n - 1; i++) {
// If we find a decrease...
if (a[i] > a[i + 1]) {
// Find cost of decrementing all to the left.
dec_cost = dec = a[i] - a[i + 1];
for (j = i - 1; j >= 0; j--) {
// Find decrement that would be needed.
dec += a[j] - a[j + 1];
// If no decement, we're done.
if (dec <= 0)
break;
// Count cost of decrement.
dec_cost += dec;
}
// Compare decrement cost with deletion cost.
if (dec_cost < a[i + 1]) {
// Decrement is cheaper. Do it.
for (j = i; j >= 0; j--) {
if (a[j] > a[i + 1])
a[j] = a[i + 1];
}
total_cost += dec_cost;
}
else {
// Deletion is cheaper. Do it.
total_cost += a[i + 1];
for (j = i + 1; j < n - 1; j++)
a[j] = a[j + 1];
--n;
}
}
}
return total_cost;
}
int main(void)
{
int a[] = { 14, 15, 16, 13, 11, 18 };
//int a[] = { 4, 3, 5, 6};
//int a[] = { 10, 3, 11, 12 };
int cost = make_nondecreasing(a, sizeof a / sizeof a[0]);
printf("cost=%d\n", cost);
return 0;
}
On Aug 27, 12:15 pm, jagadish <[email protected]> wrote:
> You are given an array of positive integers. Convert it to a sorted
> array with 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
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
