蓝桥月赛编程题：元宵节触摸灯笼大赛

创作时间:

作者:

@小白创作中心

蓝桥月赛编程题：元宵节触摸灯笼大赛

引用

CSDN

https://blog.csdn.net/zqystca/article/details/145807201

元宵节到了，小蓝决定参加村里举办的“元宵节触摸灯笼大赛”。比赛规则是这样的：村里有 M 个灯笼，排成一排，编号从 1 到 M。每个灯笼上都挂着一个谜语，小蓝需要按顺序进行猜谜语。比赛共有 N 个谜语，第 i 个谜语对应一个区间 [Li,Ri]，表示小蓝可以选择触摸这个区间内的任意一个灯笼来猜这个谜语。小蓝的手一开始放在第 1 个灯笼上（因为这是她的幸运数字）。为了猜谜语，她需要移动手去触摸灯笼。每次移动手，她都会感到“疲劳值”增加，疲劳值的计算方式是：如果她之前的手的位置是 y，现在要移动到位置 x，那么这次移动的疲劳值就是 |y−x|。小蓝的目标是猜完所有谜语，同时尽量减少总疲劳值。她不想让自己的手太累，因为猜完谜语后还要去吃汤圆呢！小蓝想知道，猜完所有谜语后，她的最小总疲劳值是多少，请你帮他计算出答案。

输入格式

第一行包含两个整数 N,M（1≤N≤105,1≤M≤109），分别表示谜语的数量和灯笼的数量。

接下来 N 行，每行包含两个整数 Li,Ri（1≤Li≤Ri≤M），表示第 i 个谜语对应的区间。

输出格式

输出一个整数，表示小蓝猜完所有谜语所需的最小总疲劳值。

样例输入

样例输出

说明

初始位置：1。
猜第一个谜语：移动到 2，疲劳值为 |1−2|=1。
猜第二个谜语：保持在 2，疲劳值为 |2−2|=0。
猜第三个谜语：移动到 3，疲劳值为 |2−3|=1。
总疲劳值为 1+0+1=2。

思路：

贪心思维，想要保证疲劳值最小，也就是移动的距离要最小。例如1 3 5，肯定要到3的位置，但是有可能会出现一种情况，当到达3位置时候，为3 1 4，如果那样写就会往后走走到1，这样是耗体力的且无用的。所以我们要比较当前位置和当前给出的最小范围，取得较大值，这就是应该走到的点。或者 3 1 2 进一步的这样要走到2。

代码实现

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const ll L = 1e5+10;
struct Node{
    ll l,r;
};
ll N,M;
Node dt[L];
int main(void)
{
    cin >> N >> M;
    for(ll i = 1 ; i <= N ; i++)
    {
        cin >> dt[i].l >> dt[i].r;	
    }
    ll cur_pos = 1;
    ll sum = 0;
    for(ll i = 1 ; i <= N ; i++)
    {
        int new_pos = min(max(cur_pos,dt[i].l),dt[i].r);
        sum += abs(new_pos - cur_pos);
        cur_pos = new_pos;
    }
    cout << sum;
    return 0;
}