[CF1696D]Permutation Graph 题解
2022/6/28 23:29:20
本文主要是介绍[CF1696D]Permutation Graph 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门(*╹▽╹*)
Preface
这是官方的 \(O(N)\) 做法,个人感觉十分优美,故记录下来。
Analysis
显然,直接建图跑最短路不可行,但我们可以转向思考必须经过的点。
容易发现,若 \(a_i = n\),那么从 \(1\) 到 \(n\) 的路径上必须要经过点 \(i\)。
考虑将 \((1,n)\) 分割成 \((1,i - 1)\) 和 \((i+1,n)\) 两部分处理。
以 \((1,i-1)\) 的部分为例,我们会发现并不需要再求出 \((1,i-1)\) 的最大最小值。
因为我们有了 \(a_i=n\),所以我们只需在 \((1,i-1)\) 中取一个使得 \(a_j\) 最小的 \(j\) 即可。
接下来就是再次分割为 \((1,j-1)\) 和 \((j+1,i)\) 处理。
\((i+1,n)\) 的部分也是同理。
可以发现这个过程并不需要任何数据结构维护,只需要前缀和后缀的最大最小值数组。
在一开始找出 \(i\) 的位置,分两次循环往 \(1\) 和 \(n\) 扫一遍就行了。
时间复杂度 \(O(N)\)。感到有点疑惑的话可以参考我的代码。
Code
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5 + 5; int n,a[maxn],pre[maxn][2],suf[maxn][2]; //0:minimum //1:maximum void work() { scanf("%d",&n); for(int i = 1;i <= n;++ i)scanf("%d",&a[i]); pre[1][0] = pre[1][1] = a[1]; for(int i = 2;i <= n;++ i)pre[i][0] = min(pre[i - 1][0] , a[i]),pre[i][1] = max(pre[i - 1][1] , a[i]); suf[n][0] = suf[n][1] = a[n]; for(int i = n - 1;i;-- i)suf[i][0] = min(suf[i + 1][0] , a[i]),suf[i][1] = max(suf[i + 1][1] , a[i]); int mid = 1,cnt = 1; for(int i = 2;i <= n;++ i) { if(a[i] == n) { mid = i; break ; } } bool cur = 0; int lst = mid; for(int i = mid - 1;i;-- i) { if(a[i] == pre[lst - 1][cur]) { ++ cnt; lst = i; cur ^= 1; } } lst = mid; cur = 0; for(int i = mid + 1;i <= n;++ i) { if(a[i] == suf[lst + 1][cur]) { ++ cnt; lst = i; cur ^= 1; } } printf("%d\n",cnt - 1); return ; } int main() { int T; scanf("%d",&T); while(T --)work(); return 0; }
完结撒花✿✿ヽ(°▽°)ノ✿
这篇关于[CF1696D]Permutation Graph 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验