連號(hào)區(qū)間數(shù)
小明這些天一直在思考這樣一個(gè)奇怪而有趣的問(wèn)題： 在1~N的某個(gè)全排列中有多少個(gè)連號(hào)區(qū)間呢？這里所說(shuō)的連號(hào)區(qū)間的定義是： 如果區(qū)間[L, R] 里的所有元素（即此排列的第L個(gè)到第R個(gè)元素）遞增排序后能得到一個(gè)長(zhǎng)度為R-L+1的“連續(xù)”數(shù)列，則稱這個(gè)區(qū)間連號(hào)區(qū)間。 當(dāng)N很小的時(shí)候，小明可以很快地算出答案，但是當(dāng)N變大的時(shí)候，問(wèn)題就不是那么簡(jiǎn)單了，現(xiàn)在小明需要你的幫助。 輸入格式
第一行是一個(gè)正整數(shù)N (1 <= N <= 50000), 表示全排列的規(guī)模。 第二行是N個(gè)不同的數(shù)字Pi(1 <= Pi <= N)， 表示這N個(gè)數(shù)字的某一全排列。 輸出格式
輸出一個(gè)整數(shù)，表示不同連號(hào)區(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]; //巧妙的一個(gè)技巧就是，如果區(qū)間的最大值(第j個(gè)數(shù)的值)-最小值(第i個(gè)數(shù)的值)剛好等于j - i 的值 if(maxn - minn == j-i){// cout << maxn << " " << minn << endl; sum++; } } } cout << sum << endl; return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
