/*標(biāo)題:連號區(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ù)目。
示例:
用戶輸入:
4
3 2 4 1
程序應(yīng)輸出:
7
用戶輸入:
5
3 4 2 5 1
程序應(yīng)輸出:
9
解釋:
第一個用例中,有7個連號區(qū)間分別是:[1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
第二個用例中,有9個連號區(qū)間分別是:[1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]
資源約定:
峰值內(nèi)存消耗(含虛擬機(jī)) < 64M
CPU消耗? < 5000ms
請嚴(yán)格按要求輸出,不要畫蛇添足地打印類似:“請您輸入...” 的多余內(nèi)容。
所有代碼放在同一個源文件中,調(diào)試通過后,拷貝提交該源碼。
注意:不要使用package語句。不要使用jdk1.6及以上版本的特性。
注意:主類的名字必須是:Main,否則按無效代碼處理。*/
//這里加入輸入:
/*用戶輸入:
4
3 2 4 1
程序應(yīng)輸出:
7
則,與之對應(yīng)的是:(3,3) (3,2) (3,2,4) (3,2,4,1) ?(2,2)? (4,4) ?(1,1)
有7個連號區(qū)間分別是:[1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
就是說從中選取一個區(qū)間,其中的數(shù)字能夠經(jīng)過全排列之后產(chǎn)生一個連續(xù)的序列
也就是max-min=count+1;
*/
//代碼參見:yibcs的
#include"stdio.h"
#include"stdlib.h"
int main()
{int i,j,k,max,min,count=0,n;
?int a[50002];
?scanf("%d",&n);
?for(i=1;i<=n;i++)
??scanf("%d",&a[i]);
?for(i=1;i<=n;i++)
?{
???? max=a[i];min=a[i];
???? for(j=i+1;j<=n;j++)
??{
??????????? if(a[j]>max)
??????????????? max=a[j];
??????????? if(a[j]<min)
??????????????? min=a[j];
???if((max-min)==(j-i))
????count++;
??}
?}
?? printf("%d\n",count+n);
printf("\n");
system("pause");}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
