题目描述
小明这些天一直在思考这样一个奇怪而有趣的问题:
在 1∼N 的某个排列中有多少个连号区间呢?
这里所说的连号区间的定义是:
如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间。
当 N 很小的时候,小明可以很快地算出答案,但是当 N 变大的时候,问题就不是那么简单了,现在小明需要你的帮助。
输入格式
第一行是一个正整数 N,表示排列的规模。
第二行是 N 个不同的数字 Pi,表示这 N 个数字的某一排列。
输出格式
输出一个整数,表示不同连号区间的数目。
数据范围
1≤N≤10000,
1≤Pi≤N
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
经参考题解后小结
一、由题目知N个数字一定是1~N且不重复出现
二、本题有一个规律,如果在一个区间满足最大值减最小值等于他们相差的位数((max-min)==(j-i))的时候可以满足题目要求,这道题目就不难解决了。
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
int main()
{
int a[10001],n,i,j,k=0,max,min;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{
max=0;
min=10000; //扫出i j之间的最大最小值
for(j=i;j<n;j++)
{
if(a[j]>max)
max=a[j];
if(a[j]<min)
min=a[j];
if(max-min==j-i)
k++;
}
}
cout<<k;
}