本文主要是介绍**360 笔试 登山者行走步数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
360 笔试 登山者的步数
分析代码如下:
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int n = 100;typedef struct Mountains
{int begin;int end;int height;/*bool operator <(const struct Mountains& other) const{return begin < other.begin;}*/
}M;
M num[n];//对应的结构体是按照 节点的end进行排序 升序 如果是相同的end情况下,则按照节点的begin排序
bool cmp(M a,M b)
{if(a.end != b.end)return a.end < b.end;elsereturn a.begin < b.begin;
}int slove()
{int sum;cin >> sum;//输入for(int i=0;i<sum;i++){cin >> num[i].begin >> num[i].end >> num[i].height;}//排序sort(num,num+sum,cmp);int k = 0;// 标记 求解断点 就是没有重合山的断点int flag[n];//断点的位置//A 作为起始点 也是一个断点 即 flag[0] = 0;memset(flag,0,sizeof(flag));int minn = 0x3f3f3f3f,cnt;//将重合部分时 那个begin的最小值记录 就是如果有多处重叠 选择起始begin最小的点for(int i=0;i<sum;i++){if(minn>num[i].begin){cnt = i;minn = num[i].begin;}}//选择断点的位置for(int i=cnt;i<sum-1;i++){//存在着缝隙 即为断点if(num[i].end < num[i+1].begin){flag[k++] = i;}}//末尾节点也是断点flag[k++] = sum-1;int maxx = 0,ans = 0;int offest = num[sum-1].end; // 横坐标的位移 不变for(int i=0;i<sum;i++){//在断点外面 就是有重合的部分 取最高的height即可maxx = max(maxx,num[i].height);if(i==flag[ans]){//断点也即区间 每个区间的求解 vertical_offestoffest += 2*maxx;maxx = 0;ans++;}}cout << offest << endl;return offest;
}
int main()
{slove();cout << "Hello world!" << endl;return 0;
}
这篇关于**360 笔试 登山者行走步数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!