連號區(qū)間數(shù)
小明這些天一直在思考這樣一個奇怪而有趣的問題： 在1~N的某個全排列中有多少個連號區(qū)間呢？這里所說的連號區(qū)間的定義是： 如果區(qū)間[L, R] 里的所有元素（即此排列的第L個到第R個元素）遞增排序后能得到一個長度為R-L+1的“連續(xù)”數(shù)列，則稱這個區(qū)間連號區(qū)間。 當(dāng)N很小的時候，小明可以很快地算出答案，但是當(dāng)N變大的時候，問題就不是那么簡單了，現(xiàn)在小明需要你的幫助。 輸入格式
第一行是一個正整數(shù)N (1 <= N <= 50000), 表示全排列的規(guī)模。 第二行是N個不同的數(shù)字Pi(1 <= Pi <= N)， 表示這N個數(shù)字的某一全排列。 輸出格式
輸出一個整數(shù)，表示不同連號區(qū)間的數(shù)目。 樣例輸入1
4 3 2 4 1 樣例輸出1
7 樣例輸入2
5 3 4 2 5 1 樣例輸出2
9
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;int a[50005],n;int main(){ cin >> n; for(int i = 0; i < n; i++)scanf("%d",&a[i]); int sum = 0; for(int i = 0;i < n; i++) { int maxn = 1; int minn = n; for(int j = i; j < n;j++) { if(a[j] > maxn)maxn = a[j]; if(minn > a[j])minn = a[j]; //巧妙的一個技巧就是，如果區(qū)間的最大值(第j個數(shù)的值)-最小值(第i個數(shù)的值)剛好等于j - i 的值 if(maxn - minn == j-i){// cout << maxn << " " << minn << endl; sum++; } } } cout << sum << endl; return 0;}新聞熱點
疑難解答
