青岛网站建设找润商,在哪个网站上做简历,被公司优化掉是什么意思,免费网络电话app下载一个数轴上共有N个点#xff0c;第一个点的坐标是度度熊现在位置#xff0c;第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。但是除了0号坐标和N-1号坐标#xff0c;他可以在其余的N-2个坐标中选出一个点#xff0c;并直接将这个点忽略掉#xff0c;问度…一个数轴上共有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 #includeiostream2 #includecstdio3 #includealgorithm4 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; iN; i)
14 {
15 cin dist[i];
16 }
17
18 int sum 0, maxDiff 0;
19 for (int i 0; iN - 1; i)
20 {
21 sum abs(dist[i] - dist[i 1]);
22 }
23
24 int diff 0;
25 for (int i 1; iN - 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