网站建设电话销售开场白,遂昌赶街网站,wordpress网站设置关键词,营销方案总结题目链接 P10904 [蓝桥杯 2024 省 C] 挖矿 - 洛谷
题目理解 我们可以将这道题中矿洞的位置理解成为一个坐标轴#xff0c;以题目样例绘出坐标轴#xff1a; 样例#xff1a; 输入的5为矿洞数量#xff0c;4为可走的步数。第二行输入是5个矿洞的坐标。输出结果为在要求步数…题目链接 P10904 [蓝桥杯 2024 省 C] 挖矿 - 洛谷
题目理解 我们可以将这道题中矿洞的位置理解成为一个坐标轴以题目样例绘出坐标轴 样例 输入的5为矿洞数量4为可走的步数。第二行输入是5个矿洞的坐标。输出结果为在要求步数内最多可采集到的单位数量的矿石。 我们下面来对样例进行分析 初始状态如下 初始位置为0剩余步数为4。当坐标0有矿石时不需要消耗步数可直接获取矿石 我们向-1移动 此时若是向负轴移动我们只能采到1个单位的矿石正轴方向可以采到2个单位。于是我们向正轴方向进发 继续进发 继续 解题思路 ——(篇幅较长大家也可以先看详细注释后的代码遇到不懂的地方再看解题思路)—— 一、核心思路概述 解决该挖矿问题的核心在于合理利用数轴上矿洞的分布信息以及移动距离限制通过巧妙的统计和计算找出在给定移动距离内能够挖掘到最多矿石的方法。主要步骤包括对矿洞坐标的分类统计、构建前缀和数组以快速计算区间矿洞数量以及全面考虑不同移动策略下的矿石获取情况。 二、具体步骤解析 一输入数据处理
1. 读取矿洞数量 n 和最大移动距离 m这两个参数将决定后续计算的范围和约束条件。
2. 依次读取 n 个矿洞在数轴上的坐标值对于每个坐标值进行如下分类处理 如果坐标值为 0说明该矿洞位于小蓝的起始位置直接将此类矿洞的计数变量 s 加 1。这些矿洞无需移动即可挖掘对最终结果有直接贡献。 如果坐标值不为 0且其绝对值小于等于 m则根据坐标值的正负性分别处理。 若坐标值为负数将其对应在负半轴的位置索引处的计数器例如数组 l加 1用于统计负半轴上在移动距离范围内的矿洞数量。 若坐标值为正数将其对应在正半轴的位置索引处的计数器例如数组 r加 1用于统计正半轴上在移动距离范围内的矿洞数量。 二构建前缀和数组 1. 对于记录负半轴矿洞数量的数组 l从索引 1 开始到 m依次计算前缀和。即 l[i] l[i - 1] l[i]这样 l[i] 就表示数轴负半轴上从 -1 到 -i 位置的矿洞总数。通过前缀和我们可以在后续计算中快速得到负半轴某一区间内的矿洞数量。 2. 同理对于记录正半轴矿洞数量的数组 r也从索引 1 开始到 m计算前缀和 r[i] r[i - 1] r[i]使得 r[i] 表示数轴正半轴上从 1 到 i 位置的矿洞总数。 三计算最大矿石获取量
1. 初始假设 首先假设最大矿石获取量 ans 为只在正半轴或只在负半轴移动时能够挖掘到的最大矿石数。即 ans max(r[m], l[m])这是一种简单的初步情况考虑因为在某些情况下仅在一个方向移动可能就能够获取最多的矿石。
2. 考虑混合移动策略 通过循环遍历 i 从 1 到 m / 2因为左右移动距离之和不能超过 m所以 i 最大取到 m / 2尝试不同的左右移动组合。 - 对于每一个 i 值计算两种混合移动策略下能够挖掘到的矿石数 先向右移动 i 单位距离再向左移动 m - 2 * i 单位距离时能够挖掘到的矿石数为 sr r[i] l[m - 2 * i]。这里 r[i] 表示向右移动 i 单位距离过程中挖掘到的正半轴矿洞数l[m - 2 * i] 表示向左移动 m - 2 * i 单位距离过程中挖掘到的负半轴矿洞数。 - 先向左移动 i 单位距离再向右移动 m - 2 * i 单位距离时能够挖掘到的矿石数为 sl l[i] r[m - 2 * i]。这里 l[i] 表示向左移动 i 单位距离过程中挖掘到的负半轴矿洞数r[m - 2 * i] 表示向右移动 m - 2 * i 单位距离过程中挖掘到的正半轴矿洞数。 每次计算出 sr 和 sl 后更新最大矿石获取量 ans即 ans max(ans, sr, sl)取当前的 ans、sr 和 sl 中的最大值作为新的 ans。
3. 加上起始点矿洞数量 最后将起始点坐标为 0的矿洞数量 s 加到 ans 中因为这些矿洞在初始位置就可获取无需移动。此时得到的 ans 即为在移动距离不超过 m 的前提下小蓝最多能获得的矿石单位数量。 通过以上步骤我们可以全面且高效地解决在给定条件下的挖矿问题找到获取最多矿石的方案。
完整代码详细注释 本文由于用到了std库中的一些函数所以作者最开始采用了CC语言代码作者用ai转化并确保代码无误后给大家放在了下面。 1.C代码
#include bits/stdc.h// 定义 solve 函数来解决挖矿问题
void solve()
{int n, m;// 从标准输入读取矿洞数量 n 和最大移动距离 mstd::cin n m;// s 用于记录坐标为 0 的矿洞数量int s 0;// 定义两个静态数组 l 和 r 来分别记录负半轴和正半轴矿洞的前缀和// 数组大小为 m 1初始化为 0int l[10000001] {0};int r[10000001] {0};// 遍历每个矿洞for (int i 0; i n; i) {int x;// 读取当前矿洞的坐标std::cin x;// 如果矿洞坐标的绝对值小于等于最大移动距离 m 且为负数//abs为绝对值函数if (std::abs(x) m x 0){// 对应负半轴的位置计数加 1l[-x];}// 如果矿洞坐标的绝对值小于等于最大移动距离 m 且为正数else if (std::abs(x) m x 0) {// 对应正半轴的位置计数加 1r[x];}// 如果矿洞坐标为 0else if (x 0) {// 坐标为 0 的矿洞数量加 1s;}}// 计算负半轴矿洞的前缀和for (int i 1; i m; i){l[i] l[i - 1];}// 计算正半轴矿洞的前缀和for (int i 1; i m; i) {r[i] r[i - 1];}// 先假设最大矿石数为只走正半轴或只走负半轴能挖到的最大矿石数int ans std::max(r[m], l[m]);// 尝试不同的左右移动组合i 表示先向一个方向移动的距离for (int i 1; i m / 2; i) {// 先向右移动 i 的距离再向左移动 m - i * 2 的距离能挖到的矿石数int sr r[i] l[m - i * 2];// 先向左移动 i 的距离再向右移动 m - i * 2 的距离能挖到的矿石数int sl l[i] r[m - i * 2];// 更新最大矿石数ans std::max({ans, sr, sl});}// 加上坐标为 0 的矿洞数量ans s;// 输出最大能获得的矿石数std::cout ans \n;
}int main()
{solve();return 0;
} 2.C语言代码
#include stdio.h
#include math.h#define MAX_M 10000001// 定义 solve 函数来解决挖矿问题
void solve() {int n, m;// 从标准输入读取矿洞数量 n 和最大移动距离 mscanf(%d %d, n, m);// s 用于记录坐标为 0 的矿洞数量int s 0;// 定义两个静态数组 l 和 r 来分别记录负半轴和正半轴矿洞的前缀和// 数组大小为 MAX_M初始化为 0int l[MAX_M] {0};int r[MAX_M] {0};// 遍历每个矿洞for (int i 0; i n; i) {int x;// 读取当前矿洞的坐标scanf(%d, x);// 如果矿洞坐标的绝对值小于等于最大移动距离 m 且为负数if (abs(x) m x 0) {// 对应负半轴的位置计数加 1l[-x];}// 如果矿洞坐标的绝对值小于等于最大移动距离 m 且为正数else if (abs(x) m x 0) {// 对应正半轴的位置计数加 1r[x];}// 如果矿洞坐标为 0else if (x 0) {// 坐标为 0 的矿洞数量加 1s;}}// 计算负半轴矿洞的前缀和for (int i 1; i m; i) {l[i] l[i - 1];}// 计算正半轴矿洞的前缀和for (int i 1; i m; i) {r[i] r[i - 1];}// 先假设最大矿石数为只走正半轴或只走负半轴能挖到的最大矿石数int ans (r[m] l[m]) ? r[m] : l[m];// 尝试不同的左右移动组合i 表示先向一个方向移动的距离for (int i 1; i m / 2; i) {// 先向右移动 i 的距离再向左移动 m - i * 2 的距离能挖到的矿石数int sr r[i] l[m - i * 2];// 先向左移动 i 的距离再向右移动 m - i * 2 的距离能挖到的矿石数int sl l[i] r[m - i * 2];// 更新最大矿石数if (sr ans) ans sr;if (sl ans) ans sl;}// 加上坐标为 0 的矿洞数量ans s;// 输出最大能获得的矿石数printf(%d\n, ans);
}int main() {solve();return 0;
} AC拿下 疑难解答 1.max函数的运用 用于比较出几个数中最大的数字大家可以简单理解为两个数比较就不需要大括号如果三个及以上的话需要大括号。
两个参数比较当比较两个值时使用 std::max(a, b) 形式这里 a 和 b 是要比较的对象不需要大括号。比如 int num1 5, num2 3; int maxNum std::max(num1, num2); 。三个及以上参数比较对于三个或更多值常使用接收初始化列表形式的重载即 std::max({val1, val2, val3,...}) 需要用大括号把这些值组成初始化列表传递给函数。像 int num1 1, num2 2, num3 3; int maxNum std::max({num1, num2, num3}); 。 ———如有问题欢迎评论区提问———
