蓝桥杯 阶乘求值【省模拟赛】
问题描述
元宵节到了,小蓝决定参加村里举办的“元宵节触摸灯笼大赛”。比赛规则是这样的:
村里有 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;
}