題目連接：http://acm.hdu.edu.cn/showproblem.php?pid=5701

題意：不解釋

題解：n^2的方法：sum[j]表示當(dāng)前枚舉的數(shù)到第j個(gè)數(shù)形成的區(qū)間里當(dāng)前數(shù)偏離中位數(shù)的程度。cnt[k]表示偏離程度為k的次數(shù)，由于k可能為負(fù)，所以預(yù)先加上n。這里我們先向右掃描，記錄cnt，再向左，當(dāng)a[j]>a[i]，則加1，否則減1。向左掃的時(shí)候，ans加上之前相同偏離程度的次數(shù)。

1 #include<cstdio> 2 #define FFC(i,a,b) for(int i=a;i<=b;++i) 3 #define FFI(i,a,b) for(int i=a;i>=b;--i) 4 5 int a[10000],n,sum[10000],cnt[20000],ans; 6 7 int main(){ 8 while(~scanf("%d",&n)){ 9 FFC(i,1,n)scanf("%d",&a[i]); 10 FFC(i,1,n){ 11 FFC(k,0,2*n)cnt[k]=0; 12 sum[i]=0,ans=cnt[n]=1; 13 FFC(j,i+1,n)sum[j]=sum[j-1]+(a[j]>a[i]?1:-1),cnt[sum[j]+n]++,ans+=(sum[j]==0); 14 FFI(j,i-1,1)sum[j]=sum[j+1]+(a[j]>a[i]?1:-1),ans+=cnt[-sum[j]+n]; 15 printf("%d%c",ans,i==n?'\n':' '); 16 } 17 } 18 return 0; 19 } View Code

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/bin-gege/p/5696146.html

總結(jié)

以上是生活随笔為你收集整理的hdu_5701_中位数计数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。