蓝桥杯 阶乘求值【省模拟赛】

问题描述

元宵节到了，小蓝决定参加村里举办的“元宵节触摸灯笼大赛”。比赛规则是这样的：

村里有 MM 个灯笼，排成一排，编号从 11 到 MM。每个灯笼上都挂着一个谜语，小蓝需要按顺序进行猜谜语。比赛共有 NN 个谜语，第 ii 个谜语对应一个区间 [Li,Ri][Li​,Ri​]，表示小蓝可以选择触摸这个区间内的任意一个灯笼来猜这个谜语。

小蓝的手一开始放在第 11 个灯笼上（因为这是她的幸运数字）。为了猜谜语，她需要移动手去触摸灯笼。每次移动手，她都会感到“疲劳值”增加，疲劳值的计算方式是：如果她之前的手的位置是 yy，现在要移动到位置 xx，那么这次移动的疲劳值就是 ∣y−x∣∣y−x∣。

小蓝的目标是猜完所有谜语，同时尽量减少总疲劳值。她不想让自己的手太累，因为猜完谜语后还要去吃汤圆呢！

小蓝想知道，猜完所有谜语后，她的最小总疲劳值是多少，请你帮他计算出答案。

输入格式

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

接下来 NN 行，每行包含两个整数 Li,Ri(1≤Li≤Ri≤M)Li​,Ri​(1≤Li​≤Ri​≤M)，表示第 ii 个谜语对应的区间。

输出格式

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

样例输入

3 5
1 3
2 4
3 5

样例输出

2

说明

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

贪心策略，能不动就不动，移动最短的距离到下一个灯谜

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N, M;
  cin>>N>>M;
  int L[N], R[N];
  for(int i=0; i<N; ++i){
    cin>>L[i]>>R[i];
  }

  long long int val = 0;
  int cur_idx = 1, next_idx = 0;
  for(int i=0; i<N; ++i){
    if(cur_idx >= L[i] && cur_idx <= R[i]){
      next_idx = cur_idx;
    }
    else if(cur_idx < L[i]){
      next_idx = L[i];
    }
    else{
      next_idx = R[i];
    }
    val += abs(next_idx - cur_idx);
    cur_idx = next_idx;
  }
  cout<<val;

  return 0;
}