主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解：P13492 【MX-X14-T2】反转时光
最后更新于 2025-07-31 10:36:54
作者
lcliruiyan
分类
题解
题解
P13492
复制 Markdown
查看原文
删除文章
更新内容
[题目传送门](https://www.luogu.com.cn/problem/P13492) ## 题目大意 这道题目要求我们找到最小的正整数 $k$，使得给定的排列 $p$ 可以通过将其划分为 $k$ 个可空子段，然后反转这些子段的顺序，最终得到一个升序排列。操作可以执行任意多次。 ## 思路 这道题的核心在于观察排列的结构，并找到关键的断点（也就是相邻元素不连续递增的位置）。通过分析这些断点的数量，我们可以确定最小的 $k$。 那么，我们如何确定 $k$ 的值呢？ 首先，我们可以统计排列中断点的数量 $t$，根据 $t$ 的值来确定 $k$。 当 $t=0$ 时，原排列已经有序，所以 $k$ 的值为 $0$。 当 $t=1$ 时，至少需要分成两段，交换顺序即可。 当 $t \ge 2$ 时，最少需要分成 $3$ 段才能成功排序。 因此，本题的代码就很简单了。 ## Code ```cpp #include<bits/stdc++.h> using namespace std; int n,p[100005]; signed main(){ cin>>n; for(int i=1;i<=n;i++) cin>>p[i]; int t=0; for(int i=1;i<n;i++) if(p[i+1]!=p[i]+1) t++; if(t==0)cout<<1; else if(t==1) cout<<2; else cout<<3; return 0; } ```
正在渲染内容...
点赞
0
收藏
0
