2024年6月GESP真题及题解(C++八级): 空间跳跃

2024年6月GESP真题及题解(C++八级): 空间跳跃

题目描述

小杨在二维空间中有n nn个水平挡板，并且挡板之间彼此不重叠，其中第i ii个挡板处于水平高度h i h_ihi​，左右端点分别位于l i l_ili​与r i r_iri​。

小杨可以在挡板上左右移动，当小杨移动到右端点时，如果再向右移动会竖直掉落，从而落到下方第一个挡板上，移动到左端点时同理。小杨在挡板上每移动1 11个单位长度会耗费1 11个单位时间，掉落时每掉落1 11个单位高度也会耗费1 11个单位时间。

小杨想知道，从第s ss个挡板上的左端点出发到第t tt个挡板需要耗费的最少时间是多少？

注意：可能无法从第s ss个挡板到达到第t tt个挡板。

输入格式

第一行包含一个正整数n nn，代表挡板数量。

第二行包含两个正整数s , t s,ts,t，含义如题面所示。

之后n nn行，每行包含三个正整数l i , r i , h i l_i,r_i,h_ili​,ri​,hi​，代表第i ii个挡板的左右端点位置与高度。

输出格式

输出一个整数代表需要耗费的最少时间，如果无法到达则输出− 1 -1−1。

输入输出样例 1

输入 1

3 3 1 5 6 3 3 5 6 1 4 100000

输出 1

100001

说明/提示

样例解释

耗费时间最少的移动方案为，从第3 33个挡板左端点移动到右端点，耗费3 33个单位时间，然后向右移动掉落到第2 22个挡板上，耗费100000 − 6 = 99994 100000-6=99994100000−6=99994个单位时间，之后再向右移动1 11个单位长度，耗费1 11个单位时间，最后向右移动掉落到第1 11个挡板上，耗费3 33个单位时间。共耗费100001 100001100001个单位时间。

数据范围

对于全部数据，保证有1 ≤ n ≤ 1000 1\leq n\leq 10001≤n≤1000，1 ≤ l i ≤ r i ≤ 10 5 1\leq l_i\leq r_i\leq 10^51≤li​≤ri​≤105，1 ≤ h i ≤ 10 5 1\leq h_i\leq 10^51≤hi​≤105。

思路分析

核心思路

• 将每个挡板的左、右端点抽象为图中的节点，共2n个。
• 边分为三类：
  1. 挡板内部移动：连接同一挡板的左右端点，权重为挡板长度。
  2. 从左端点掉落：根据下落规则，连接到下方第一个挡板的左右端点，权重为下落高度加水平移动距离。
  3. 从右端点掉落：同理处理。
• 通过 Dijkstra 算法计算从起点（第 s 挡板左端点）到所有节点的最短时间。
• 最后，综合两种方式更新到达每个挡板的最短时间：
  • 通过直接到达该挡板的某个端点。
  • 通过从上方某个端点直接掉落到该挡板（不移动到端点）。

关键点

1. 下方第一个挡板的预处理：对于每个端点，遍历所有挡板找到满足条件的最大高度挡板，O(n²) 在 n≤1000 时可行。
2. 掉落边的权重计算：准确计算下落高度和从落点到目标端点的水平移动距离。
3. 终点处理：最终答案不是到某个端点的距离，而是到整个挡板的最短时间，因此需要额外更新每个挡板的最短到达时间。

复杂度

• 时间复杂度：O(n² + E log V)，其中 V=2n，E≤4n（每个端点最多两条掉落边）+ n（内部边），总体可接受。
• 空间复杂度：O(n²) 主要用于存储图和距离数组。

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constll INF=1e18;// 足够大的无穷大intmain(){intn,s,t;cin>>n>>s>>t;vector<int>l(n+1),r(n+1),h(n+1);for(inti=1;i<=n;i++){cin>>l[i]>>r[i]>>h[i];}// 预处理每个挡板左端点和右端点的下方第一个挡板vector<int>down_l(n+1,0),down_r(n+1,0);for(inti=1;i<=n;i++){// 左端点intbest_h=-1;for(intj=1;j<=n;j++){if(j==i)continue;if(h[j]<h[i]&&l[j]<=l[i]&&l[i]<=r[j]){if(h[j]>best_h){best_h=h[j];down_l[i]=j;}}}// 右端点best_h=-1;for(intj=1;j<=n;j++){if(j==i)continue;if(h[j]<h[i]&&l[j]<=r[i]&&r[i]<=r[j]){if(h[j]>best_h){best_h=h[j];down_r[i]=j;}}}}// 建图：节点编号 1..n 为左端点，n+1..2n 为右端点intN=2*n;// 总节点数vector<vector<pair<int,ll>>>adj(N+1);// 1. 每个挡板内部左右移动for(inti=1;i<=n;i++){intw=r[i]-l[i];adj[i].push_back({i+n,w});adj[i+n].push_back({i,w});}// 2. 从左端点掉落for(inti=1;i<=n;i++){if(down_l[i]){intj=down_l[i];// 落到 j 的左端点ll w1=(h[i]-h[j])+(l[i]-l[j]);adj[i].push_back({j,w1});// 落到 j 的右端点ll w2=(h[i]-h[j])+(r[j]-l[i]);adj[i].push_back({j+n,w2});}}// 3. 从右端点掉落for(inti=1;i<=n;i++){if(down_r[i]){intj=down_r[i];// 落到 j 的左端点ll w1=(h[i]-h[j])+(r[i]-l[j]);adj[i+n].push_back({j,w1});// 落到 j 的右端点ll w2=(h[i]-h[j])+(r[j]-r[i]);adj[i+n].push_back({j+n,w2});}}// Dijkstravector<ll>dist(N+1,INF);intstart=s;// 起点为第 s 挡板的左端点，节点编号 sdist[start]=0;priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;pq.push({0,start});while(!pq.empty()){auto[d,u]=pq.top();pq.pop();if(d!=dist[u])continue;for(auto[v,w]:adj[u]){if(dist[v]>d+w){dist[v]=d+w;pq.push({dist[v],v});}}}// 计算到达每个挡板的最小时间vector<ll>ans(n+1,INF);// 通过端点更新for(intu=1;u<=N;u++){if(dist[u]==INF)continue;intplate;if(u<=n)plate=u;elseplate=u-n;ans[plate]=min(ans[plate],dist[u]);}// 通过直接掉落更新for(inti=1;i<=n;i++){// 从左端点掉落if(down_l[i]&&dist[i]<INF){intj=down_l[i];ans[j]=min(ans[j],dist[i]+(h[i]-h[j]));}// 从右端点掉落if(down_r[i]&&dist[i+n]<INF){intj=down_r[i];ans[j]=min(ans[j],dist[i+n]+(h[i]-h[j]));}}// 输出答案if(ans[t]==INF)cout<<-1<<endl;elsecout<<ans[t]<<endl;return0;}

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}