请教一道算法题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道算法题

请教一道算法题# JobHunting - 待字闺中

m*a2014-11-26 08:11

1 楼

Give an integer array, adjust each integers so that the difference of every
adjacent integers are not greater than a given number target. If the array
before adjustment is A, the array after adjustment is B, you should minimize
the sum of abs(A[i] - B[i])
You can assume each number in the array is a positive integer and not
greater than 100
Example:
Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the
adjustment cost is 2 and it's minimal. Return 2.
题目如上，请问大牛们有没有好的想法？谢谢！

x*k2014-11-26 08:11

2 楼

感觉像leetcode的candy问题？

t*y2014-11-26 08:11

3 楼

动态规划

m*k2014-11-26 08:11

4 楼

>>Given [1,4,2,3] and target=1, one of the solutions is >>[2,3,2,3], the
>>adjustment cost is 2 and it's minimal. Return 2.
结果为啥不是[1,2,2,3] ， adjust cost = 1 ?

b*g2014-11-26 08:11

5 楼

4>2所以adjust以后也得是这个关系？
mark，回头想想

【在 m*****k 的大作中提到】

: >>Given [1,4,2,3] and target=1, one of the solutions is >>[2,3,2,3], the
: >>adjustment cost is 2 and it's minimal. Return 2.
: 结果为啥不是[1,2,2,3] ， adjust cost = 1 ?

m*a2014-11-26 08:11

6 楼

这个cost是2，第二个元素由4变成了2了

【在 m*****k 的大作中提到】

: >>Given [1,4,2,3] and target=1, one of the solutions is >>[2,3,2,3], the
: >>adjustment cost is 2 and it's minimal. Return 2.
: 结果为啥不是[1,2,2,3] ， adjust cost = 1 ?

m*a2014-11-26 08:11

7 楼

能详细点么？

【在 t*******y 的大作中提到】

: 动态规划

m*a2014-11-26 08:11

8 楼

这个没有规定adjust后还是原来的大小关系吧

【在 b******g 的大作中提到】

: 4>2所以adjust以后也得是这个关系？
: mark，回头想想

r*72014-11-26 08:11

9 楼

复杂度太高了
应该要用到正数和小于100的特点，不过目前还没想到啥好办法

【在 t*******y 的大作中提到】

: 动态规划

i*o2014-11-26 08:11

10 楼

不是排版的变种?

g*s2014-11-26 08:11

11 楼

复杂度也就100N，
100的特点就是target就算是无穷大也和100一样。

★ 发自iPhone App: ChineseWeb 8.6

【在 r****7 的大作中提到】

: 复杂度太高了
: 应该要用到正数和小于100的特点，不过目前还没想到啥好办法

r*72014-11-26 08:11

12 楼

恩，后来睡觉的时候想了想，100就是为了限制一个constant time的，否则是个NP
problem

【在 g***s 的大作中提到】

: 复杂度也就100N，
: 100的特点就是target就算是无穷大也和100一样。
:
: ★ 发自iPhone App: ChineseWeb 8.6

m*a2014-11-26 08:11

13 楼

动态规划是怎么做得呢？能详细一点么？

【在 r****7 的大作中提到】

: 恩，后来睡觉的时候想了想，100就是为了限制一个constant time的，否则是个NP
: problem

s*c2014-11-26 08:11

14 楼

dfs+pruning,你看成不成。数大小都在100以内，复杂度就能估计，可还是太狠

every
minimize

【在 m******a 的大作中提到】

: Give an integer array, adjust each integers so that the difference of every
: adjacent integers are not greater than a given number target. If the array
: before adjustment is A, the array after adjustment is B, you should minimize
: the sum of abs(A[i] - B[i])
: You can assume each number in the array is a positive integer and not
: greater than 100
: Example:
: Given [1,4,2,3] and target=1, one of the solutions is [2,3,2,3], the
: adjustment cost is 2 and it's minimal. Return 2.
: 题目如上，请问大牛们有没有好的想法？谢谢！

x*92014-11-26 08:11

15 楼

略暴力，Lintcode上的题。（没看错，是Lintcode，不是Leetcode）
class Solution {
public:
/**
* @param A: An integer array.
* @param target: An integer.
*/
int MinAdjustmentCost(vector A, int target) {
if (A.empty()) {
return 0;
}
int n = A.size();
int ptr = 0;
memset(dp, 0, sizeof(dp));

for (int i = 0; i < n; i++) {
int cur = A[i];
int next = ptr ^ 1;
memset(dp[next], INF, sizeof(dp[next]));
for (int j = 1; j <= 100; j++) {
int diff = abs(cur - j);
int range_l = max(1, j - target);
int range_r = min(100, j + target);
for (int k = range_l; k <= range_r; k++) {
dp[next][j] = min(dp[next][j], dp[ptr][k] + diff);
}
}
ptr ^= 1;
}
int ans = INF;
for (int i = 1; i <= SIZE; i++) {
ans = min(ans, dp[ptr][i]);
}
return ans;
}
private:
static const int SIZE = 100;
static const int INF = 0x3f3f3f3f;
int dp[2][SIZE + 5];
};

b*r2014-11-26 08:11

16 楼

my 2 cents for DP, define min as cost of between i and j, inclusive.
min(i,j)=min(i,k)+min(k,j), ii am guessing probably that's the reason why the array element has a range
limit.
by the way the solution is not unique, e.g, both 2,3,2,3 and 1,2,2,3 work

d*82014-11-26 08:11

17 楼

Using Dynamic Programming.
The time complexity is O(maxDiff * N), where N is array size and maxDiff is
the maximum diff allowed between adjacent elements
My codes here:
http://ideone.com/btd3WU