HDU1394(權值線段樹)

題意：

給定一個0到n-1的數字組成的序列，可以將序列進行左移任意次，求所能組成序列的逆序對的最小值

題解：

利用權值線段樹，我們先求出當前序列所能組成的逆序對，
然后依次左移動
當a[i]在第一位時，a[i]的貢獻為a[i]個 (因為序列由0到n-1組成的，a[i]在第一位，說明比a[i]小的由a[i]個)
當a[i]移動到最后一位，貢獻為：(n-1)-a[i]
這樣貢獻的變化為(n-1)-a[i]-a[i]
比如序列：
2 4 6 1 3 5 0
2在第一位，比2小的有兩個
左移后
4 6 1 3 5 0 2
2在最后一位，前面比2大的有(7-1)-2=4

代碼：

代碼中序列處理位1~n

#include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> using namespace std; const int maxx = 5005; int tree[maxx<<2]; inline int L(int root){return root<<1;}; inline int R(int root){return root<<1|1;}; inline int MID(int l,int r){return (l+r)>>1;}; int a[maxx]; void update(int root,int l,int r,int pos){if (l==r){tree[root]++;return;}int mid=MID(l,r);if (pos<=mid){update(L(root),l,mid,pos);}else {update(R(root),mid+1,r,pos);}tree[root]=tree[L(root)]+tree[R(root)]; } int query(int root,int l,int r,int ql,int qr){if (ql<=l && r<=qr){return tree[root];}int mid=MID(l,r);if (qr<=mid){return query(L(root),l,mid,ql,qr);}else if (ql>mid){return query(R(root),mid+1,r,ql,qr);}else {return query(L(root),l,mid,ql,qr)+query(R(root),mid+1,r,ql,qr);} } int main(){int n;while(~scanf("%d",&n)){int ans=0;memset(tree,0,sizeof(tree));for (int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]++;ans+=query(1,1,n,a[i],n);//查看在a[i]前面比a[i]大的數有多少（求逆序對和） update(1,1,n,a[i]);//插入a[i] }int minn=ans;for (int i=1;i<=n;i++){ans=ans+(n-a[i])-(a[i]-1);minn=min(ans,minn);}printf("%d\n",minn);}return 0; }

總結

以上是生活随笔為你收集整理的HDU1394(权值线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。