868
藍橋杯 曆屆試題 連號區間數
曆屆試題 連號區間數時間限製：1.0s 內存限製：256.0MB
問題描述
小明這些天一直在思考這樣一個奇怪而有趣的問題：
在1~N的某個全排列中有多少個連號區間呢？這裏所說的連號區間的定義是：
如果區間[L, R] 裏的所有元素（即此排列的第L個到第R個元素）遞增排序後能得到一個長度為
R-L+1的“連續”數列，則稱這個區間連號區間。
當N很小的時候，小明可以很快地算出答案，但是當N變大的時候，問題就不是那麼簡單了，現在
小明需要你的幫助。
輸入格式
第一行是一個正整數N (1 <= N <= 50000), 表示全排列的規模。
第二行是N個不同的數字Pi(1 <= Pi <= N)， 表示這N個數字的某一全排列。
輸出格式
輸出一個整數，表示不同連號區間的數目。
樣例輸入1
4
3 2 4 1
樣例輸出1
7
樣例輸入2
5
3 4 2 5 1
樣例輸出2
9
//是某個全排列的連號區間，不是所有！
#include<stdio.h>
int a[50010];
int main()
{
int i,j,n,L,R,sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
sum++;
L=a[i];R=a[i];
for(j=i+1;j<n;j++)
{
if(a[j]>R)
R=a[j];
if(a[j]<L)
L=a[j];
if(R-L==j-i)
sum++;
}
}
printf("%d\n",sum);
return 0;
}
最後更新：2017-04-03 12:54:48