*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;
    else
        return 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_offest
            offest += 2*maxx;
            maxx = 0;
            ans++;
        }
    }

    cout << offest << endl;
    return offest;
}
int main()
{
    slove();
    cout << "Hello world!" << endl;
    return 0;
}