首页 > 代码库 > hdu 1394 Minimum Inversion Number
hdu 1394 Minimum Inversion Number
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394
思路:先求逆序数,然后有个技巧(真坑)......用线段树或者树状数组都可以做。移位的技巧就是逆序数是减少ant[i],而增加n-1-ant[i]的.
#include <iostream>#include <cstring> #include <cstdio> #define MAXSIZE 500000using namespace std;struct node{ int l,r; int sum;}tree[MAXSIZE*4];void build(int root,int l,int r){ tree[root].l = l; tree[root].r = r; if(l == r) { return; } int mid = (l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r);}void update(int root,int pos,int value){ if(tree[root].r == tree[root].l&&tree[root].l == pos) { tree[root].sum += value; return; } int mid = (tree[root].r+tree[root].l)/2; if(pos>mid) { update(root*2+1,pos,value); } if(pos<=mid) { update(root*2,pos,value); } tree[root].sum = tree[root*2].sum + tree[root*2+1].sum; }int query(int root,int l,int r){ if(tree[root].l==l&&tree[root].r==r) { return tree[root].sum; } int mid = (tree[root].r +tree[root].l)/2; if(r<=mid) { query(root*2,l,r); } else if(l>mid) { query(root*2+1,l,r); } else { int a = query(root*2,l,mid); int b = query(root*2+1,mid+1,r); return a+b; } }int main(){// freopen("data.txt","r",stdin); int n; int sum; int res; int ant[5500]; while(scanf("%d",&n)!=EOF) { memset(ant,0,sizeof(ant)); memset(tree,0,sizeof(tree)); build(1,0,n); sum = 0; for(int i=1;i<=n;i++) { scanf("%d",&ant[i]); sum += query(1,ant[i]+1,n); update(1,ant[i],1); } res = sum; for(int i = 1;i<=n;i++) { sum = sum+n-2*ant[i]-1; res = min(sum,res); } printf("%d\n",res); } return 0;}
还有个错误。。。wrong了我俩小时。。就是线段树build的时候要开到n不然会溢出。。。
hdu 1394 Minimum Inversion Number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。