第1题-分拣中心

题目内容

某快递分拣中心有  个分拣口，编号从 1 到 。包裹一开始放在 1 号口，需要送到  号口。

每个分拣口都配置了一条传送带：若包裹当前停在第  号口，可以支付 1 次跳转费用，把它送到闭区间  内的任意一个分拣口（任意整数位  满足 ）。

请计算：把包裹从 1 号口送到  号口，最少需要几次跳转。若怎样跳都到不了，则视为无解。

输入描述

第一行一个整数  ()，表示询问组数。

接着共有  组数据，每一组格式如下：

第一行一个整数  ()，表示分拣口个数。

第二行  个整数 。

第三行  个整数 。

保证对每个  都有 ，且同一文件中所有  之和不超过 。

输出描述

输出一行，包含  个整数，相邻整数之间用单个空格隔开。

第  个数表示第  组询问的答案：最少跳转次数；若无法送达则输出 -1。

样例1

输入

362 3 5 6 6 64 5 6 6 6 641 1 1 42 2 2 4111

输出

2 -1 0

说明

第一组：。一条最优路线是 ，共跳 2 次；也可走 ，同样是 2 次。

第二组：从 1 号口只能在  之间往返，永远进不了 4 号口，故为 -1。

第三组：起点即终点，无需跳转，答案为 0。

题目分析

经典的区间跳跃问题，通用且高效的方法是使用贪心算法（Greedy Algorithm），其思想类似于经典的“跳跃游戏 II”（Jump Game II）。

1. 问题模型：

• 处于位置 ，可以跳到区间  内的任意位置。
• 目标是求从  到  的最少步数。
• 这是一个求无权图最短路径的问题。由于每次跳跃的代价都是 1，且我们要找最少次数，这符合贪心策略的特征：在每一步中，尽可能扩大我们能到达的范围。

2. 贪心

• current_reach：当前这一步（第 steps 步）最远能跳到的右边界。
• max_reach：在当前这一步的范围内，所有点能跳到的最远右边界。
• 当遍历完 current_reach 范围内的所有点时，必须再跳一步（steps++），此时新的边界就是 max_reach。
• 维护两个变量：
• 时间复杂度：只需要遍历一次数组，复杂度为 ，对于  的数据量非常合适。

3. 特殊情况处理：

• 如果起点等于终点 ()，直接输出 0。
• 如果某一步无法扩展最远距离（即 max_reach <= current_reach），说明无法到达终点，输出 -1。

C++ 代码实现

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;voidsolve(){int m;if (!(cin >> m)) return;vector<int> a(m + 1), b(m + 1);for (int i = 1; i <= m; ++i) {cin >> a[i];    }for (int i = 1; i <= m; ++i) {cin >> b[i];    }if (m == 1) {cout << 0 << " ";return;    }int steps = 0;          // 记录步数int current_reach = 1;  // 当前这一步能到达的最远位置（初始在位置1）int max_reach = 1;      // 下一步能到达的最远位置// 遍历当前位置能到达的所有点// 需要遍历到 current_reach，因为站在 current_reach 上也能跳for (int i = 1; i <= current_reach; ++i) {// 更新从位置 i 能跳到的最远距离        max_reach = max(max_reach, b[i]);// 如果已经能直接跳到终点 m 或更远if (max_reach >= m) {            steps++;cout << steps << " ";return;        }// 如果遍历完了当前这一步的所有可能位置if (i == current_reach) {// 如果最远距离没有增加，说明卡住了，无法前进if (max_reach <= current_reach) {cout << -1 << " ";return;            }// 必须跳一步，更新当前能到达的边界            current_reach = max_reach;            steps++;        }    }cout << -1 << " ";}intmain(){    ios_base::sync_with_stdio(false);cin.tie(NULL);int g;if (cin >> g) {while (g--) {            solve();        }    }cout << endl; return0;}

第2题-分差达标最长列

题目内容

监测系统记录了一串长度为  的读数 ，并给定正整数门槛 。

从中挑出若干读数（保持相对先后次序）组成一条监测列。称这条监测列分差达标，当且仅当：在其中任意取出三个互不相同下标上的读数 ，都有

若挑出的读数不足三个，则直接判定为分差达标。

请求出：原读数序列里，分差达标的监测列最长能有多长。

[说明] 这里的监测列对应从原序列删去若干项（也可一个都不删）后剩下的序列。

输入描述

第一行一个整数  ()，表示询问组数。

接下来共有  组数据，每一组格式如下：

第一行一个整数  ()，表示读数个数。

第二行一个整数  ()，表示分差门槛。

第三行  个整数  ()，表示各次读数。

保证同一文件内所有  之和不超过 。

输出描述

输出一行，包含  个整数，相邻整数之间用单个空格隔开。

第  个数表示第  组询问中，分差达标监测列的最大长度。

样例1

输入

3683 7 1 12 4 931001 2 35610 10 10 10 10

输出

5 2 2

说明

第一组：门槛 。取读数 （对应原序列去掉 4）长度为 5，任意三个读数的两两绝对差之和不小于 8；若六个全取，则  不满足条件。

第二组：只有三个读数且两两绝对差之和为 4，小于 100，故最长只能取 2。

第三组：全部读数相同，任意三个都不达标，故最长为 2。

题目分析

本题主要考察对数学性质的观察以及贪心策略的应用。

1. 核心条件转化题目要求选出的序列中，任意三个数  满足：

假设我们将选出的数从小到大排序为 。

代入原式：

所以，题目的核心条件等价于：在选出的序列中，任意两个数的差的绝对值（即最大值减最小值）必须满足 。

2. 贪心策略为了让选出的序列尽可能长，需要让数字之间“尽可能紧凑”但又“满足间距”。

• 如果我们对原数组进行排序，那么问题就变成了：在一个有序数组中，最多能选出多少个数，使得相邻选出的两个数之差 。
• 为什么可以排序？ 题目条件是“任意取出三个...都有...”。这个条件是关于数值大小的全局性质，与下标顺序无关。只要数值集合满足条件，无论怎么排列都满足。为了求最大长度，可以打乱顺序重新组合，因此排序是合法的。

3. 算法流程

1. 将数组从小到大排序。
2. 使用贪心算法：
• 前两个数直接选入。
• 从左到右遍历剩余元素，设当前数为 x
• 如果 x 与倒数第二个已选数的差至少为    就选入 x
3. 统计选中的个数。

C++ 代码实现

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;voidsolve(){int m;longlong w;if (!(cin >> m)) return;cin >> w;vector<longlong> v(m);for (int i = 0; i < m; ++i) {cin >> v[i];    }// 不足三个数直接判定为分差达标if (m <= 2) {cout << m << " ";return;    }    sort(v.begin(), v.end());// 条件等价于：排序后的子序列中 sub[i] - sub[i-2] >= w/2int count = 2;                 // 先选前两个最小的，给后面留最大空间longlong last_2 = v[0];       // 上上个选中的数longlong last_1 = v[1];       // 上个选中的数for (int i = 2; i < m; ++i) {if (2 * (v[i] - last_2) >= w) {            count++;            last_2 = last_1;       // 状态滚动：上上个 <- 上个，上个 <- 当前            last_1 = v[i];        }    }cout << count << " ";}intmain(){    ios_base::sync_with_stdio(false);cin.tie(NULL);int g;if (cin >> g) {while (g--) {            solve();        }    }cout << endl;return0;}

复杂度分析

• 时间复杂度：主要消耗在排序上，为 。贪心遍历只需要 。对于 ，完全可以在 1 秒内运行完成。
• 空间复杂度： 用于存储数组。

扫码立即报名

https://www.saikr.com/vse/Math26?ces=XB42377