当前位置: 首页 > article >正文

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

问题描述

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

村里有 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;
}


http://www.kler.cn/a/586755.html

相关文章:

  • 谷歌Chrome或微软Edge浏览器修改网页任意内容
  • C++笔记-类与对象(中)
  • 二分+前缀和/滑动窗口——成绩统计
  • 神经网络:定义与核心原理
  • 基于 Verilog 的多路复用显示驱动设计与测试:实践与探索
  • Visual Studio里的调试(debugging)功能介绍
  • Tomato靶机
  • Vue 中的 v-for 如何遍历对象?
  • 【模拟算法】
  • misc19~21
  • 如何在AVL树中高效插入并保持平衡:一步步掌握旋转与平衡因子 —— 旋转篇
  • ​​​​​​​大语言模型安全风险分析及相关解决方案
  • P3379 【模板】最近公共祖先(LCA)【题解】(倍增法)
  • 链表·简单归并
  • OpenBMC:BmcWeb添加路由3 设置权限
  • 机器学习 Day05 pandas库
  • Linux 系统蓝牙音频服务实现分析
  • 基于深度学习的蛀牙智能检测与语音提示系统【python源码+Pyqt5界面+数据集+训练代码】
  • C语言数据类型取值范围及格式化符号
  • CentOS 8 停止维护后通过 rpm 包手动安装 docker