Inverse Pair
生活随笔
收集整理的這篇文章主要介紹了
Inverse Pair
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
Inverse Pair
題意：
一個(gè)數(shù)組a，現(xiàn)在構(gòu)造一個(gè)數(shù)組c，c[i]=a[i]+0/1（0或1），使得c的逆序?qū)ψ钌?/p>
題解：
如果x在x+1的后面，我們讓x這個(gè)數(shù)+1,x+1不變，就可以讓逆序?qū)ι?。如果x在x+1后面，我們就認(rèn)為連邊(x+1,x),x也有可能與x-1連邊，形成一個(gè)長度為L的鏈，那減少的逆序?qū)?shù)量就是L/2
代碼：
//還是自己菜最后還是看了網(wǎng)上模板才寫出來的#include <bits/stdc++.h>#define LL long long using namespace std;const int N=3e6+10; LL num[N],a[N]; LL ans; void Merge(int l,int mid,int r) //分治的治 合并是求逆序?qū)Φ年P(guān)鍵 {int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(num[i]>num[j]) //前半部分中比num[i]大的數(shù)都比num[j]大，將num[j]放在num[i]前面的話，逆序數(shù)要加上mid+1-i{a[k++]=num[j++];ans+=mid-i+1; //統(tǒng)計(jì)逆序?qū)?/span>}else //這里這情況不產(chǎn)生逆序?qū)?/span>a[k++]=num[i++];}while(i<=mid)a[k++]=num[i++];while(j<=r)a[k++]=num[j++];for(int e=l;e<=r;e++) //將這次操作完的num數(shù)組更新num[e]=a[e]; }void Merge_sort(int l,int r) //分治的分 在這里不斷地把一個(gè)串細(xì)分然后回溯合并 {if(l<r){int mid=(l+r)/2;Merge_sort(l,mid);Merge_sort(mid+1,r);Merge(l,mid,r);} } int vis[N]; int main() {int n;cin>>n;int tot=0;for(int i=0;i<n;i++){cin>>num[i];if(vis[num[i]+1]){tot++;}else vis[num[i]]=1;}ans=0;Merge_sort(0,n-1); //cout<<ans<<endl;cout<<ans-tot;return 0; } /* 8 8 1 6 3 4 5 2 7 */總結(jié)
以上是生活随笔為你收集整理的Inverse Pair的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 酒大黄功效与作用
- 下一篇： P4551 最长异或路径