当前位置：首页 > news >正文

柠檬笔试——野猪骑士

news 2025/8/9 6:37:30

题目：

野猪骑士最近在一条路上锻炼，整条路可以被分作n块地块，每个地块有自己的高度hi,i∈{1,2,3,...,n}。野猪骑士在地块i时，会跳向下标比i大且高度比hi严格大的地块的集合中高度最小的地块。野猪骑士希望知道自己在每个地块上的下一跳的目的地的高度，如果下一跳不存在的话，则记为-1。

其目的是求比当前下标大的值中的最小值。

①set方法

直接用STL库里的 set，其不仅去重而且排序，逆序遍历数据（保证 set 中的值对应下标都大于当前下标），用 unpper_bound 找到容器中第一个严格大于当前值的值即可。

#include <iostream>
#include <vector>
#include <set>using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n = 8;vector<int> height = { 11, 13, 10, 5, 10, 12, 21, 11 };vector<int> ans(n, 0);set<int> mySet;for (int i = n - 1; i >= 0; --i) {if (mySet.empty()) {ans[i] = -1;}else {auto it = mySet.upper_bound(height[i]);if (it != mySet.end()) {ans[i] = *it;}else {ans[i] = -1;}}mySet.insert(height[i]);}for (int x : ans) {cout << x << " ";}return 0;
}

测试结果：

12 21 11 10 11 21 -1 -1

②单调栈方法

本题是可以使用单调栈的。由于单调栈是找最近的第一个大的数，所以直接使用会导致出错。但是当把下标和高度绑定后，升序排序高度，此时逆序对整个数组使用单调栈，就保证高度大于当前高度，这样得到的第一个大的数（下标）即为答案。不过注意，当高度相同时，需要将下标降序处理，优先处理下标较小的跳跃高度，否则下标大时可能会时栈处理为空，再处理小下标时则没有数据可用。如果思路模糊可以使用代码模拟一遍。

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>using namespace std;bool compare(vector<int>& a, vector<int>& b) {if (a[0] == b[0]) {return a[1] > b[1];}else {return a[0] < b[0];}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n = 8;vector<int> height = { 11, 13, 10, 5, 10, 12, 21, 11 };vector<int> ans(n, 0);vector<vector<int>> u(n, vector<int>(2, 0));for (int i = 0; i < n; i++) {u[i][1] = i;u[i][0] = height[i];}sort(u.begin(), u.end(), compare);stack<int> stk;for (int i = n - 1; i >= 0; --i) {if (stk.empty()) {ans[u[i][1]] = -1;}else {while (!stk.empty() &&  u[i][1] > stk.top()) {stk.pop();}if (stk.empty()) {ans[u[i][1]] = -1;}else {ans[u[i][1]] = height[stk.top()];}}stk.push(u[i][1]);}for (int x : ans) {cout << x << " ";}return 0;
}

测试结果：