連號區間數
小明這些天一直在思考這樣一個奇怪而有趣的問題： 在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 <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]; //巧妙的一個技巧就是，如果區間的最大值(第j個數的值)-最小值(第i個數的值)剛好等于j - i 的值 if(maxn - minn == j-i){// cout << maxn << " " << minn << endl; sum++; } } } cout << sum << endl; return 0;}新聞熱點
疑難解答
