连号区间数
小明这些天一直在思考这样一个奇怪而有趣的问题：
在 1∼N 的某个排列中有多少个连号区间呢？
这里所说的连号区间的定义是：
如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。
当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
输入格式
第一行是一个正整数 N，表示排列的规模。
第二行是 N 个不同的数字 Pi，表示这 N 个数字的某一排列。
输出格式
输出一个整数，表示不同连号区间的数目。
数据范围
1≤N≤10000,
1≤Pi≤N
输入样例1：
4
3 2 4 1
输出样例1：
7
输入样例2：
5
3 4 2 5 1
输出样例2：
9
样例解释
第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二个用例中，有 9 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]
时/空限制：1s / 64MB
总通过数：8851
总尝试数：14791
来源：第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组
算法思路
这个题的关键是 看懂题目 题目里面说的是 在 1∼N 的某个排列 这个排列的意思是 没有重复的数字
也就是说 如果 一段连续的数字 最大的数字 - 最小的数字 = 这段数字的长度 - 1那么代表这段数字
是符合题目要求的 因为没有重复的数字
提交代码
C++
/* 这个题的关键是 看懂题目 题目里面说的是 在 1∼N 的某个排列 这个排列的意思是 没有重复的数字 也就是说 如果 一段连续的数字 最大的数字 - 最小的数字 = 这段数字的长度 - 1那么代表这段数字 是符合题目要求的 因为没有重复的数字 */ #include<bits/stdc++.h> using namespace std; int INF = 1e9; const int N = 10010; int a[N]; int res; int main() { int n; cin >> n; for (int i = 0; i < n; ++ i) scanf ("%d", &a[i]); for (int i = 0; i < n; ++ i) { int mav = -INF, miv = INF; int j; for (j = i; j < n; ++ j) { mav = max(mav, a[j]); miv = min(miv, a[j]); if (mav - miv == j - i) res ++; } } cout << res; return 0; }
Java
import java.util.*; import java.io.*; public class Main { static int INF = (int)1e9; static int [] a = new int [10010]; static int res, n; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(reader.readLine()); String [] strs = reader.readLine().split(" "); for (int i = 0; i < n; ++ i) a[i] = Integer.parseInt(strs[i]); for (int i = 0; i < n; ++ i) { int j; int mav = -INF, miv = INF; for (j = i; j < n; ++ j) { mav = Math.max(mav, a[j]); miv = Math.min(miv, a[j]); if (mav - miv == j - i) res ++; } } System.out.println(res); } }
