首页 > 试题广场 >

度度熊回家

[编程题]度度熊回家
  • 热度指数：10459 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一个数轴上共有N个点，第一个点的坐标是度度熊现在位置，第N-1个点是度度熊的家。现在他需要依次的从0号坐标走到N-1号坐标。
但是除了0号坐标和N-1号坐标，他可以在其余的N-2个坐标中选出一个点，并直接将这个点忽略掉，问度度熊回家至少走多少距离？

输入描述:
输入一个正整数N, N <= 50。

接下来N个整数表示坐标，正数表示X轴的正方向，负数表示X轴的负方向。绝对值小于等于100


输出描述:
输出一个整数表示度度熊最少需要走的距离。
示例1

输入

4
1 4 -1 3

输出

4
算法知识视频讲解
添加回答
若轩头像 若轩
为什么我觉得题描述不清楚，没看懂，求解
发表于 2017-06-27 17:35:18 回复(7)
7厘海岸头像 7厘海岸 
#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;
}
这道题一开始我是每看明白的，以为是按排序后的坐标来计算距离，后面才发现，是按未排序数组的坐标来计算。

发表于 2017-08-12 12:39:26 回复(7)
天蓝何头像 天蓝何

说一下自己的思路。在若干点中选择一点，使全程的路程最小。其实说白了就是选择一点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;
}
发表于 2017-09-10 11:17:33 回复(0)
rs勿忘初心头像 rs勿忘初心 
#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;
}

编辑于 2017-04-30 11:17:31 回复(7)
=.=头像 =.= 
/*
简单说下自己的思路：
    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);
    }
}

发表于 2017-05-08 16:46:30 回复(2)
夜未艾头像 夜未艾
import java.util.Scanner;
import java.lang.Math;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n = input.nextInt();
        int point[] = new int[n];
        for(int i=0;i<n;i++){
            point[i] = input.nextInt();
        }
        int sum =0;
        for(int i=0;i<n-1;i++){
//求不删除任何点的距离
            sum += Math.abs(point[i+1]-point[i]);
        }
        int distance =0;
        for(int i =1;i<n-1;i++){
        //求删除某点缩短的距离取最大值
            int del = Math.abs(point[i+1]-point[i])+Math.abs(point[i]-point[i-1])-Math.abs(point[i+1]-point[i-1]);
            if(del>distance){
                distance =del;
            }
        }
        System.out.println(sum-distance);
    }
}
发表于 2017-05-12 16:24:01 回复(0)
CH加冕头像 CH加冕 
 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);
    }
编辑于 2018-09-14 09:48:26 回复(0)
未来的搬运工头像 未来的搬运工 
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]));
    }


}
发表于 2017-07-18 09:38:08 回复(0)
人生就是这样啊头像 人生就是这样啊 
#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;
}

发表于 2017-04-30 14:13:45 回复(3)
包子山头像 包子山 
//借鉴各位大神的思路
#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;
}

发表于 2019-09-16 21:39:30 回复(0)
kobe666头像 kobe666 
//来个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; 
}

发表于 2019-03-10 20:24:25 回复(0)
JavaScript
Let＇sRoad头像 Let＇sRoad 
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]);

编辑于 2018-04-13 01:20:04 回复(0)
元气の悟空头像 元气の悟空 
#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);
}

发表于 2017-11-09 11:06:48 回复(0)
讨喜头像 讨喜 


	
	

		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);
	


	

		    }
	


	

		}
发表于 2017-10-11 14:06:27 回复(0)
未之未央丿头像 未之未央丿

import java.util.Scanner;

/**

  • Created by TaoHaoWei on 2017/9/25.
  • 本人新建博客：www.mynight.top
  • 欢迎交友和指正 ^_^
    */
    public class Main {
    public static void main(String[] args) {
     {
     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);
 }
    }
    }
发表于 2017-09-25 10:35:10 回复(0)
FIRE★PeterらJackson头像 FIRE★PeterらJackson
#include<iostream>
#include<vector>
#include<algorithm>
intmis(inta,intb)
{
    if(a>b)
    returna-b;
    else
    returnb-a;
}
using namespace std;
intmain()
{
    intN,i,j=0,a,z=0,s=0;
    cin>>N;  vector<int>v1;
    vector<int>v2;
    s=N;
    while(N--)
    {
        cin>>a;
        v1.push_back(a);
    }
    for(i=1;i<s;i++)
    {
        for(j=0;j<s;j++)
        {
            if(j+1==i)
            {
                z=z+mis(v1[j+2],v1[j]);
                //cout<<z<<" "<<"shu"<<endl;
                j++;
            }
            else
            z=z+mis(v1[j+1],v1[j]);
            if((j+2)==s){
                v2.push_back(z);
                    //cout<<z<<endl;
                    z=0;
                break;
            }
        }
    }
    sort(v2.begin(),v2.end());
    cout<<v2[0]<<endl;
}
发表于 2017-09-02 22:50:01 回复(0)
咖啡阿爸头像 咖啡阿爸 

	   /**





	         *这道题的意思就是，随机去掉除了第一个和最后一个的点，问最终距离最小的是多少？ 





	         * 比如　输入的是１　－２　３　４，去掉－２和３这两个点，看距离最小的是多少





	         * 去掉－２，数组是1 3 4，距离是：３－１＋４－３＝２＋１＝３





	         * 去掉３，数组是：1 -2 4 ，距离是－２－１的绝对值加上４－（－２）为３＋６为９





	  　　　　* 最终最小距离是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]);




	    }




	       




	}

发表于 2017-08-28 11:51:37 回复(0)
liberty_zheng头像 liberty_zheng 
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
发表于 2017-08-16 20:50:53 回复(0)
Java
一份希望要怎么放进心脏-头像 一份希望要怎么放进心脏-

发表于 2017-08-10 10:14:25 回复(0)
陶琳头像 陶琳 
//运行通过，但有一点：输入控制，如注释，用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;
}

发表于 2017-07-17 16:41:35 回复(2)
提交观点

问题信息

贪心 模拟 数学
难度：
121条回答 16283浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号