題目鏈接：點(diǎn)擊查看

題目大意：線段樹求逆序數(shù)，給出的數(shù)列可以組成環(huán)，問怎么樣求可以讓逆序數(shù)最小，輸出最小值

題目分析：看到這個(gè)題的第一反應(yīng)是暴力枚舉5000種情況，因?yàn)楦杏X這個(gè)題的N給的不是很大，但是仔細(xì)一想應(yīng)該是個(gè)N*N*logN的時(shí)間復(fù)雜度，一下子到了1e8，肯定是穩(wěn)穩(wěn)的T了，就沒去嘗試，這個(gè)題目最關(guān)鍵的點(diǎn)是找到逆序數(shù)的關(guān)系，做過這么多有關(guān)逆序數(shù)的題目，都是變形題目，但是本質(zhì)是不變的，我們可以這樣分析，每次給出的數(shù)都是0~n-1，則設(shè)第i個(gè)數(shù)為a[i]，那么在n個(gè)數(shù)中，除去它本身還有n-1個(gè)數(shù)，比它本身小的有a[i]-1個(gè)數(shù)，比它本身大的有n-1-(a[i]-1)個(gè)數(shù)，那么我們?nèi)绻麑⒌谝粋€(gè)數(shù)移動(dòng)到了最后一位，我們可以分步來考慮：

先將第一個(gè)數(shù)刪除，那么在它后面有a[i]-1個(gè)數(shù)比它小，即新數(shù)列的逆序數(shù)會(huì)減少a[i]-1

再將剛剛被刪除的數(shù)加在最后一位，則它的前面現(xiàn)在有了n-1-(a[i]-1)個(gè)數(shù)比它大，即新數(shù)列的逆序數(shù)會(huì)增加n-1-(a[i]-1)

綜上所述，每一次數(shù)列所組成的環(huán)轉(zhuǎn)動(dòng)一個(gè)單位，逆序數(shù)就會(huì)在之前的基礎(chǔ)上增加n-1-(a[i]-1)-(a[i]-1)，化簡得到n-2*a[i]+1

注意：有個(gè)細(xì)節(jié)就是它給出的數(shù)列是0~n-1，我們可以給每一項(xiàng)都加1來完成我們上述的結(jié)論，加上我這個(gè)題偷懶用樹狀數(shù)組寫的，所以只能從1開始，具體的會(huì)在注釋中說明，上代碼：

#include<iostream>#include<cstdio> #include<string>#include<cstring>#include<algorithm>#include<stack>#include<queue>#include<map>#include<sstream>#include<cmath>using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5050;int n;int c[N],a[N];int lowbit(int x){return x&-x;}void update(int pos){while(pos<=n){c[pos]++;pos+=lowbit(pos);}}int query(int pos){int ans=0;while(pos){ans+=c[pos];pos-=lowbit(pos);}return ans;}int main(){// freopen("input.txt","r",stdin);while(scanf("%d",&n)!=EOF){memset(c,0,sizeof(c));for(int i=1;i<=n;i++){scanf("%d",a+i);a[i]++;//因?yàn)閿?shù)列是從0開始，所以統(tǒng)一向右偏移一個(gè)單位，保證所有的數(shù)都為正數(shù)}int ans=0;for(int i=1;i<=n;i++){ans+=query(n)-query(a[i]);update(a[i]);} int mmin=ans;for(int i=1;i<=n;i++){ans=ans+n-2*a[i]+1;mmin=min(mmin,ans);}cout<<mmin<<endl;}return 0;}

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 1394 Minimum Inversion Number(树状数组)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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