一个数轴上共有N个点,第一个点的坐标是度度熊现在位置,第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。
但是除了0号坐标和N-1号坐标,他可以在其余的N-2个坐标中选出一个点,并直接将这个点忽略掉,问度度熊回家至少走多少距离?
输入一个正整数N, N <= 50。
接下来N个整数表示坐标,正数表示X轴的正方向,负数表示X轴的负方向。绝对值小于等于100
输出一个整数表示度度熊最少需要走的距离。
4 1 4 -1 3
4
#include<iostream> #include<algorithm> #include<cmath> using namespace std; int main() { int n, a[50]; while (cin >> n) { int i, ans = 0; for (i = 0; i < n; i++) { cin >> a[i]; /* 计算两个相邻节点之间的距离,ans为所有相邻节点距离的总和 */ if (i) ans += abs(a[i] - a[i - 1]); } int _m = 0; //计算相邻的3个节点之间的距离总和,A->B,B->C,A->C for (i = 0; i < n - 2; i++) _m = max(_m, abs(a[i] - a[i + 1]) + abs(a[i + 1] - a[i + 2]) - abs(a[i] - a[i + 2])); cout << ans - _m << endl;//_m属于重复计算 } return 0; }
说一下自己的思路。在若干点中选择一点,使全程的路程最小。其实说白了就是选择一点i,使其缩小的距离最大,即原来的距离是dis(i-1,i)+dis(i,i+1),去掉点i之后的距离是dis(i-1,i+1),只要遍历一遍,求出每个点上面两个距离的差值,求最大值,就可以确定要忽略哪个点了
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> vec(n);
for (int &i : vec)
cin >> i;
int max = 0;
int index = -1;
int yuanlai;
int houlai;
for (vector<int>::size_type i = 1; i < n - 1; ++i) {
yuanlai = abs(vec[i] - vec[i - 1]) + abs(vec[i] - vec[i + 1]);
houlai = abs(vec[i - 1] - vec[i + 1]);
if (yuanlai - houlai > max) {
max = yuanlai - houlai;
index = i;
}
}
if(index!=-1)
vec.erase(vec.begin() + index);
int sum = 0;
for (vector<int>::size_type i = 0; i < vec.size()-1; ++i)
sum += abs(vec[i] - vec[i + 1]);
cout << sum;
return 0;
}
#include<iostream> using namespace std; int MinRoad(int *a,int i,int n) { int sum=0; for(int j=0;j<n-1;j++) //注意这里是j<n-1,可以自己在草稿纸上分析 { if(j+1==i) { sum+=abs(a[j+2]-a[j]); j++; } else sum+=abs(a[j+1]-a[j]); } return sum; } int main() { int n,temp,sum=65536; int *a=new int[n]; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=1;i<n-1;i++) //依次删除a[1]和a[n-1]其中一个元素,来求距离 { temp=MinRoad(a,i,n); if(sum>temp) sum=temp; } cout<<sum<<endl; }
/* 简单说下自己的思路: 1.题目的意思就是笨笨熊从第一个点依次走到最后一个点,中间可以去除一个点不走。 2.解题思路:枚举(通常枚举是最笨的方法,唉) 3.首先排除特殊情况 一个点和两个点 4.把所有的路线列举出来,然后计算每一条路线的总长度 5.比较之后,求出最短路线 6.打印结果 */ import java.util.*; import java.lang.*; public class Main{ public static void main(String args[]){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] dian = new int[n]; for(int i=0; i<n; i++){ dian[i] = sc.nextInt(); } if(n<=1){ System.out.println(0); } if(n==2){ System.out.println(Math.abs(dian[1]-dian[0])); } int distancce = 0; for(int i=1; i<=n-2; i++){ int temp = 0; for(int j=0; j<n-1; j++){ if(j+1 == i){ temp += Math.abs(dian[j+2] - dian[j]); j++; } else{ temp += Math.abs(dian[j+1] - dian[j]); } } if(i==1){ distancce = temp; } else{ if(temp < distancce){ distancce = temp; } } } System.out.println(distancce); } }
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] arr = new int[n];
int[] sortArr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scan.nextInt();
sortArr[i] = arr[i];
}
int length=0;
//不做优化要走的距离
for(int i=0; i<arr.length-1;i++){
length+=Math.abs(arr[i]-arr[i+1]);
}
int minLength=length;
int[] newArr=new int[n-1];
//逐个测试去掉一个点后的所需要走的距离
for(int sub=1; sub<arr.length-1; sub++){
//构造去掉一个点后的新数组
for(int newArrIndex=0;newArrIndex<newArr.length;newArrIndex++){
if(newArrIndex>=sub){
newArr[newArrIndex]=arr[newArrIndex+1];
}
else {
newArr[newArrIndex]=arr[newArrIndex];
}
}
int len=0;
//计算去掉一个点后的所需要走的距离
for(int k=0; k<newArr.length-1;k++){
len+=Math.abs(newArr[k]-newArr[k+1]);
}
//取到最小距离
if(len<minLength){
minLength=len;
}
}
System.out.println(minLength);
}
import java.util.Scanner; public class Order { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int num = scanner.nextInt(); int[] n = new int[num]; for (int i = 0; i < num; i++) { n[i]=scanner.nextInt(); } int start = n[0],end = n[num-1],useless = 0,sum = 0,use = 0; for (int i = 1; i < num-1; i++) { sum += Math.abs(n[i]-n[i-1]);//总距离 if(!(n[i]>Math.min(start,end)&&n[i]<Math.max(start,end))){//当所处的点不在起点和终点之间时,才开始计算多余的距离 int abs = Math.abs(n[i-1]-n[i])+Math.abs(n[i]-n[i+1]);//求出当前点多走的距离 if(useless<abs){//求出最大的无用距离 useless = Math.abs(n[i-1]-n[i])+Math.abs(n[i]-n[i+1]); use = Math.abs(n[i+1]-n[i-1]);//若删除当前节点,求出删除后上一个节点到当前的节点的距离 } } } System.out.println(sum-useless+use+Math.abs(n[num-1]-n[num-2])); } }
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, temp; cin >> N; vector<int> nums; for (int i = 0; i < N; i++){ cin >> temp; nums.push_back(temp); } int len = nums.size(); int max_cha = 0, cha, pos = 1, result = 0; for (int i = 1; i < len - 1; i++){ result += abs(nums[i] - nums[i - 1]); cha = abs(nums[i] - nums[i - 1]) + abs(nums[i + 1] - nums[i]) - abs(nums[i + 1] - nums[i - 1]); if (cha > max_cha){ max_cha = cha; pos = i; } } result += abs(nums[len - 1] - nums[len - 2]); result -= max_cha; cout << result << endl; cin.get(); cin.get(); return 0; }
//借鉴各位大神的思路 #include <iostream> #include <algorithm> using namespace std; int main() { int n,a[50]; int x = 0,length = 0;; cin >> n; while(n--) cin >> a[x++]; for(int i = 1;i<x;i++) { length += abs(a[i]-a[i-1]); } int max = 0; for(int j = 0;j<x-2;j++) { int temp = abs(a[j]-a[j+1])+abs(a[j+1]-a[j+2])-abs(a[j]-a[j+2]); if(temp >max) max = temp; } cout << length - max << endl; return 0; }
//来个php的吧 思路是借鉴上边的
public function getDistance($disArr) { $n = count($disArr); //总距离 $sum=0; for ($i=0;$i$n;$i++){ if(!isset($disArr[$i+1])) break; //总距离 $sum += abs($disArr[$i+1]-$disArr[$i]); } //求出最大的多走的距离 $plusDistanceMax=0; for($i=0;$i$n-2;$i++) { $plusDistance = abs($disArr[$i]-$disArr[$i+1])+abs($disArr[$i+1]-$disArr[$i+2])-abs($disArr[$i]-$disArr[$i+2]); if($plusDistance>$plusDistanceMax) $plusDistanceMax=$plusDistance; } $distance = $sum-$plusDistanceMax; return $distance; }
function distance(num, arr){ var result = []; var result1 = []; var result2 = []; var sum1 = 0; var sum2 = 0; result = arr.splice(0, num-2).concat(arr.slice(-1)); result.forEach(function(ele){ if (ele > 0) { result1.push(ele) }else{ result2.push(ele) } }) result1.sort(function(a, b){ return a - b }) result2.sort(function(a, b){ return a - b }) if (result1[arguments.length-1] + result2[0] > 0 || 'string') { result1.pop(); }else{ result2.shift(); } result1.forEach(function(ele){ sum1 += ele; }) result2.forEach(function(ele){ sum2 += ele; }) console.log(sum1 + sum2); } distance(4, [1, 4, -1, 3]);
#include<stdio.h> #include<math.h> #define min(a,b) a<b?a:b int a[55],n,i; int getDis(){ int dis=0; for(int i=1;i<n;i++) dis+=(int)fabs(a[i]-a[i-1]); return dis; } int main(){ for(scanf("%d",&n),i=0;i<n;i++) scanf("%d",a+i); int Min=getDis(); for(i=1;i<=n-2;i++){ int temp=a[i]; a[i]=a[i-1],Min=min(Min,getDis()),a[i]=temp; } printf("%d\n",Min); }
importjava.util.*;publicclassMain{publicstaticvoidmain(String[] args) {//接收参数Scanner sc =newScanner(System.in);intcount = sc.nextInt();List<Integer> list =newArrayList<>();for(inti =0; i < count; i++) {list.add(sc.nextInt());}//分析:找出第i项,该项为(和i+1的差的绝对值<abs()>加上和i-1的差的绝对值)最大的项 ,把该项去除intmax =0;intindex =0;for(inti =1; i < list.size()-1; i++){if(Math.abs(list.get(i)-list.get(i-1))+Math.abs(list.get(i)-list.get(i+1)) > max){max = Math.abs(list.get(i)-list.get(i-1))+Math.abs(list.get(i)-list.get(i+1));index = i;}}list.remove(list.get(index));//计算步数intstep =0;for(inti =0; i < list.size()-1; i++) {step+=Math.abs(list.get(i)-list.get(i+1));}System.out.println(step);}}
import java.util.Scanner;
/**
{
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int step[] = new int[n];
for (int i=0;i<n;i++)
step[i] = in.nextInt();
int dp[] = new int[n];//1到n-2;
int max = 1;
for (int i=1;i<n-1;i++)
{
dp[i] = Math.abs(step[i]-step[i-1])+Math.abs(step[i]-step[i+1]);
if(dp[i]>dp[max])max = i;
}
step[max] = step[max-1];
int sum = 0;
for (int i=1;i<n;i++)
{
sum += Math.abs(step[i]-step[i-1]);
}
System.out.println(sum);
}
}/***这道题的意思就是,随机去掉除了第一个和最后一个的点,问最终距离最小的是多少?* 比如 输入的是1 -2 3 4,去掉-2和3这两个点,看距离最小的是多少* 去掉-2,数组是1 3 4,距离是:3-1+4-3=2+1=3* 去掉3,数组是:1 -2 4 ,距离是-2-1的绝对值加上4-(-2)为3+6为9* 最终最小距离是3*/importjava.lang.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[] args){Scanner sc=newScanner(System.in);intcount=sc.nextInt();Integer[] nums=newInteger[count];for(inti=0;i<count;i++){nums[i]=sc.nextInt();}int[] result=newint[count-2];for(inti=1;i<count-1;i++){ //i为除了第一个和最后一个点intsum=0;for(intj=1;j<count;j++){if(j==i){sum+=Math.abs(nums[j+1]-nums[j-1]) ; //遇到了需要去掉的点,就计算这个点后面的点减去他前面点的距离。j++;}else{sum+=Math.abs(nums[j]-nums[j-1]);}}result[i-1]=sum;}Arrays.sort(result);System.out.println(result[0]);}}
input() data=map(int,raw_input().split(' ')) nearst=max(data)*len(data) def get_distance(x): distance=0 current=data[0] for i in range(1,len(x)): distance+=abs(x[i]-current) current=x[i] return distance for i in range(1,len(data)-1): tem=data[:i]+data[i+1:] if get_distance(tem)<nearst: nearst=get_distance(tem) print nearst
//运行通过,但有一点:输入控制,如注释,用while会报一个段错误,不明原因,还望指教
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int main(){
int N;
// int position;
while(cin>>N){
int a[N];
vector<int> sum;
int i = 0;
for(i=0; i<N; i++)
cin>>a[i];
// while(N--){
// cin>>position;
// a[i] = position;
// i++;
// }
i = 0;
for(int j=1; j<N-1; j++){
for(int m=0; m<N-1; m++){
if(m+1 == j){
i += abs(a[m+2]-a[m]);
m++;
}
else
i += abs(a[m+1]-a[m]);
}
sum.push_back(i);
i = 0;
}
sort(sum.begin(), sum.end());
cout<<sum[0]<<endl;
}
return 0;
}