连号区间数 暴力

张开发
• 2026/4/18 19:50:12 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

连号区间数 暴力
连号区间数题目描述小明这些天一直在思考这样一个奇怪而有趣的问题在1 11~N NN的某个全排列中有多少个连号区间呢这里所说的连号区间的定义是如果区间[ L , R ] [L, R][L,R]里的所有元素即此排列的第L LL个到第R RR个元素递增排序后能得到一个长度为R − L 1 R - L 1R−L1的连续数列则称这个区间连号区间。当N NN很小的时候小明可以很快地算出答案但是当N NN变大的时候问题就不是那么简单了现在小明需要你的帮助。输入描述第一行是一个正整数N ( 1 ≤ N ≤ 50 × 10 4 ) N (1 \leq N \leq 50 \times 10^4)N(1≤N≤50×104), 表示全排列的规模。第二行是N NN个不同的数字P i ( 1 ≤ P i ≤ N ) P_i (1 \leq P_i \leq N)Pi​(1≤Pi​≤N)表示这N NN个数字的某一全排列。输出描述输出一个整数表示不同连号区间的数目。输入输出样例示例输入4 3 2 4 1输出7运行限制最大运行时间5s最大运行内存: 64M题目分析题目为给你一个数组是 1~N 的一个排列没有重复找出有多少个子区间 [L, R] 是“连续数”举例3241区间[1,3]→324排序后234, 是一个连续数通过观察我们可以知道m a x − m i n R − L max - min R - Lmax−minR−L所以我们可以枚举所有区间检验m a x − m i n R − L max - min R - Lmax−minR−L如果相等则该区间满足要求代码如下#includebits/stdc.husingnamespacestd;intmain(){intn;cinn;vectorintp(n);for(inti0;in;i){cinp[i];}longlongans0;for(intl0;ln;l){intmnp[l],mxp[l];for(intrl;rn;r){mnmin(mn,p[r]);mxmax(mx,p[r]);if(mx-mnr-l){ans;}}}coutansendl;return0;}

更多文章