专栏文章
题解:P13993 【MX-X19-T2】「LAOI-14」SPECIALZ
P13993题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minzle8l
- 此快照首次捕获于
- 2025/12/02 10:56 3 个月前
- 此快照最后确认于
- 2025/12/02 10:56 3 个月前
P13993 【MX-X19-T2】「LAOI-14」SPECIALZ
题目概括
有一个 行 列的矩阵,每行格子的数值都由 构成。有一个机器人在 的位置,他会循环执行下列操作:
- 在 行时以自身位置向左和向右数 个格子,移动到其中数值最大的格子上。
- 向下移动一格,保持列数不变,直到超出矩阵最后一行。
可以自由组合每行的元素,使得机器人经过的格子数值之和最小,求出这个值。
思路
首先,对于每次向下移动后,因为每行格子的数值都是 的,所以想要取到 ,就必须在刚移到新行时就经过 。
其次,由于机器人每次都会在自己左边 个格子和自己右边 个格子中寻找最大的数值,所以我们只需要将最小的几个数放到机器人的左右,每次就可以取到最小值。
可以看出来我们每次横向移动答案都是加上 ( 是可遍历的格子个数)。
而在横向移动时是有多个可移动的点位的,但是我们为了使得每次机器人遍历到的区间最小,需要移动到最靠近边界的地方。
结论
- 每到一个新的行,。
- 计算左右可遍历的格子数量 ,更新答案 。
- 在左右可遍历的最远格子中选择最靠近边界的格子,更新位置。
代码
其他小细节都标注在注释里了。
CPP#include <bits/stdc++.h>
using namespace std;
int n,m;
long long ans; //这里一定要 long long 哦~
int pos=1; //初始位置 1
int k[500005];
int main(){
cin >> n >> m;
for (int i=1;i<=n;i++) //读入每行的 k
cin >> k[i];
for (int i=1;i<=n;i++){
int l=1,r=m; //这里其实不必要,看着好看
int sl,sr,s; //左右可遍历的格子数量和总的数量
int nposl,nposr; //左右最远达到的位置
sl=min(pos-l,k[i]); //计算数量,不超边界
sr=min(r-pos,k[i]); //同上
s=sl+sr;
ans+=1; //每次换行都 +1
ans+=s+1; //计算横向移动答案
if (sl==0) //已经在边界的时候不能原地不动
nposl=pos+1;
else
nposl=pos-sl;
if (sr==0) //同上
nposr=pos-1;
else
nposr=pos+sr;
if (nposl-l<r-nposr) //看哪个离边界近
pos=nposl; //更新位置
else
pos=nposr; //更新位置
}
cout << ans; //输出答案
return 0;
}
如果有不会的部分可以试着以我的方法推导一下样例,过一遍就会了。
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...