输入一个正整数N, N <= 50。
接下来N个整数表示坐标,正数表示X轴的正方向,负数表示X轴的负方向。绝对值小于等于100
输出一个整数表示度度熊最少需要走的距离。
4 1 4 -1 3
4
import java.util.Scanner; public class Main{ public static void main(String[] argus){ Scanner sc = new Scanner(System.in); int num = sc.nextInt(); int[] point = new int[num]; for(int i = 0; i<num; i++){ point[i] = sc.nextInt(); } int before = 0; int after = 0; int Max = 0; for(int j = 1; j<num-1; j++){ before = Math.abs(point[j-1]-point[j])+Math.abs(point[j]-point[j+1]); after = Math.abs(point[j-1]-point[j+1]); if(before - after > Max){ Max = before - after; } } int sum = 0; for(int k = 1; k<num; k++){ sum += Math.abs(point[k] - point[k-1]); } sum = sum - Max; System.out.print(sum); sc.close(); } }很简单题目
o(n)的时间复杂度
public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] array = new int[n]; for (int i = 0; i < n; i++) { array[i] = in.nextInt(); } int max = 0; int sum = 0, temp1, temp2; for (int i = 0; i < n - 2; i++) { temp1 = array[i + 1] - array[i]; temp2 = array[i + 2] - array[i + 1]; sum += Math.abs(temp1); if (((temp1 ^ temp2) >>> 31) == 1) {//判断是否异号 max = Math.max(Math.abs(temp1 - temp2) - Math.abs(array[i + 2] - array[i]), max); } } sum += Math.abs(array[n - 1] - array[n - 2]);//加上最后一组数据 System.out.println(sum - max); } }
import java.io.BufferedReader;import java.io.IOException;
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int length=scanner.nextInt();
int[]arrays=new int[length];
for(int i=0;i<length;i++){
arrays[i]=scanner.nextInt();
}
int max=0;
int useless=0;
int sum=0;
for(int i=1;i<length-1;i++) {
//先计算不去掉i点时3个点之间的距离
int dis = Math.abs(arrays[i]-arrays[i-1])+Math.abs(arrays[i+1]-arrays[i]);
//顺便计算sum,未包括最后一点的距离
sum += Math.abs(arrays[i]-arrays[i-1]);
//在计算去掉i点之后两点的距离
int undis = Math.abs(arrays[i-1]-arrays[i+1]);
int d = Math.abs(dis-undis);
//差值最大的点为可去掉的点
if(d>max){
max = d;
useless = i;
}
}
if(useless!=0){
sum = sum +Math.abs(arrays[length-1]-arrays[length-2])
- Math.abs(arrays[useless]-arrays[useless-1])
-Math.abs(arrays[useless+1]-arrays[useless])
+Math.abs(arrays[useless-1]-arrays[useless+1]);
}else{
sum = sum+Math.abs(arrays[length-1]-arrays[length-2]);
}
System.out.println(sum);
}