首页 > 代码库 > HDU 1394 Minimum Inversion Number
HDU 1394 Minimum Inversion Number
题意是求逆序数。
先无脑用线段树求出原数列的逆序数。
然后:
不过是把一个数列的第一个数放到最后。这样重复n-1次。在新数列中找出最小的逆序数。
假如第一个数是 a[i] 那么放到最后之后,新数列的逆序数为原数列的逆序数减去比 a[i]小的数,加上比 a[i]大的数。
即 ans=ans-2*a[i]+n-1; 这样就必须把输入的数列存下来。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<bitset> #include<vector> #include<cmath> #define INF 0x7fffffff #define eps 1e-8 #define LL long long #define PI 3.141592654 #define CLR(a,b) memset(a,b,sizeof(a)) #define FOR(i,a,b) for(int i=a;i<b;i++) #define FOR_(i,a,b) for(int i=a;i>=b;i--) #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define mp make_pair #define ft first #define sd second #define sf scanf #define pf printf #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() #define acfun std::ios::sync_with_stdio(false) #define SIZE 5000 +1 #define MOD 1000000007 using namespace std; struct lx { int a,p; void init(int aa,int pp) { a=aa,p=pp; } bool friend operator < (lx a,lx b) { return a.a>b.a; } }; lx l[SIZE]; int n; int t[SIZE*4]; int site; void update(int o,int l,int r) { if(l==r)t[o]=1; else { int m=(l+r)>>1; if(site<=m)update(o*2,l,m); else update(o*2+1,m+1,r); t[o]=t[o*2]+t[o*2+1]; } } int ql,qr; int query(int o,int l,int r) { if(l>=ql&&r<=qr)return t[o]; int m=(l+r)>>1; int ans=0; if(ql<=m)ans+=query(o*2,l,m); if(qr>m)ans+=query(o*2+1,m+1,r); return ans; } int main() { while(~sf("%d",&n)) { int a[SIZE]; FOR(i,1,n+1) { sf("%d",&l[i].a); a[i]=l[i].a; l[i].p=i; } sort(l+1,l+n+1); CLR(t,0); int ans=0; FOR(i,1,n+1) { site=l[i].p; update(1,1,n); ql=1,qr=site-1; if(ql<=qr) ans+=query(1,1,n); } //pf("%d\n",ans); // -a[i] +(n-1-a[i]) int tmp=ans; FOR(i,1,n) { tmp=tmp-2*a[i]+n-1; ans=min(ans,tmp); //pf("%d\n",tmp); } pf("%d\n",ans); } }
HDU 1394 Minimum Inversion Number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。