一個數軸上共有N個點，第一個點的坐標是度度熊現在位置，第N-1個點是度度熊的家。現在他需要依次的從0號坐標走到N-1號坐標。
但是除了0號坐標和N-1號坐標，他可以在其余的N-2個坐標中選出一個點，并直接將這個點忽略掉，問度度熊回家至少走多少距離？?
輸入描述:

輸入一個正整數N, N <= 50。 接下來N個整數表示坐標，正數表示X軸的正方向，負數表示X軸的負方向。絕對值小于等于100

輸出描述:

輸出一個整數表示度度熊最少需要走的距離。

輸入例子:

4 1 4 -1 3

輸出例子:

4

思路：這題的關鍵在如何找到可以去除的那一點。考察連續的三個點，若三點的值都是遞增的，如{1,2,5}，這樣，從第一點到第三點的距離為4；當不是遞增的時候，如（2,1,5），那我們只要跳過第二點，就可以得到最短距離為3，如何得到這點了？暴力解法，枚舉出缺某一點時，可以省下的距離，然后和一步步走的時候距離相減，就可以得到最短的距離。代碼如下：

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 7 int main() 8 { 9 int N; 10 cin >> N; 11 12 int dist[50]; 13 for (int i = 0; i<N; i++) 14 { 15 cin >> dist[i]; 16 } 17 18 int sum = 0, maxDiff = 0; 19 for (int i = 0; i<N - 1; i++) 20 { 21 sum += abs(dist[i] - dist[i + 1]); 22 } 23 24 int diff = 0; 25 for (int i = 1; i<N - 1; i++) 26 { 27 diff = abs(dist[i - 1] - dist[i]) + abs(dist[i] - dist[i + 1]); 28 diff-=abs(dist[i - 1] - dist[i + 1]); 29 maxDiff = max(maxDiff, diff); //省下的最大距離 30 } 31 sum -= maxDiff; 32 cout << sum; 33 return 0; 34 }

Ref：

http://m.blog.csdn.net/Double2hao/article/details/72459499

轉載于:https://www.cnblogs.com/love-yh/p/7421797.html

總結

以上是生活随笔為你收集整理的度度熊回家的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。