度度熊回家问题

xiaoxiao2021-02-28  108

这个题目说实话我自己看了半个小时没看懂,后来请教了同学,然后他给的解释及题目如图所示

好吧,看了人家给的解释,自己在本地编辑运性了大概半个小时,终于写出来啦,没有用什么特殊的算法,最蠢的办法来的。

#include <iostream> #include <vector> using namespace std; int main() { int n; cin>>n; int arr[n]; int tmp=0; int store=0; for(int i=0;i<n;i++) cin>>arr[i]; //这个向量用来存储忽略N-2个点中其中一个后,每种方法需要走的步数 //最后再给这个向量进行排序,从小到大,然后返回res[0]就ok了 //这里面主要就是依次忽略下标从1-N-2的数 //我的方法是,两层循环 //外循环,代表依次忽略arr[1],arr[2],.....arr[N-2] //内层循环就是从下标0-N-1,但是,这里我要注意两种情况 //由于我计算步数的方法是,相邻两个点之差的绝对值,这种方法很简单 //但是要跳过某一个数,我的方法是在内层循环用了两个if语句 //这两个if语句表示,如果当前点比要忽略的点差1,则,直接求解abs(arr[j+2]-arr[j]) //但是如果下一次循环,刚好我的当前点就是要忽略的那个点,那直接没有任何操作,continue即可 //这里我每次外循环执行一次后都给tmp置为0,因为他是来临时存储每忽略一个数,所需要的步数,在将他放入结果数组后,就可以置0 vector<int> res; for(int i=1;i<n-1;i++) { tmp=0; for(int j=0;j<n-1;j++) { if(i==j+1) { tmp+=abs(arr[j+2]-arr[j]); //cout<<"abs(arr["<<j+2<<"]-arr["<<j<<"])="<<tmp<<endl; continue; } if(i==j) { continue; } tmp+=abs(arr[j]-arr[j+1]); //cout<<"abs(arr["<<j<<"]-arr["<<j+1<<"])="<<tmp<<endl; //cout<<tmp<<endl; } res.push_back(tmp); } /* for(int i=0; i<res.size();i++) cout<<res[i]<<endl; */ for(int i=1; i<=res.size()-1;i++) { for(int j=0;j<res.size()-i;j++) { if(res[j]>res[j+1]) { int t=res[j]; res[j]=res[j+1]; res[j+1]=t; } } } /* for(int i=0; i<res.size();i++) cout<<res[i]<<endl; */ cout<<res[0]<<endl; return 0; }

转载请注明原文地址: https://www.6miu.com/read-47176.html

最新回复(0)