cf351B Jeff and Furik (树状数组)

逆序对数=0的时候,这个数列是有序的

然后交换相邻的,看哪个比较大,逆序对数会加1或减1

Jeff用的是最优策略所以他肯定让逆序对数-1

设f[i]表示Jeff操作前,逆序对数为i,最终的期望次数

那就有$f[i]=0.5f[i-2]+0.5f[i]+2$

以及$f[1]=1,f[0]=0$

可以得出$f[i]=4*floor(i/2)+(i\&1)$

 #pragma GCC optimize(3)
#include<bits/stdc++.h>
#define pa pair<ll,ll>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=; inline char gc(){
return getchar();
static const int maxs=<<;static char buf[maxs],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
ll x=;char c=gc();bool neg=;
while(c<''||c>''){if(c=='-') neg=;c=gc();}
while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=gc();
return neg?(~x+):x;
} int N,a[maxn];
int tr[maxn]; inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y){
for(;x<=N;x+=lowbit(x)) tr[x]+=y;
}
inline int query(int x){
int re=;for(;x;x-=lowbit(x)) re+=tr[x];return re;
} int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd();
for(i=;i<=N;i++) a[i]=rd();
int num=;
for(i=;i<=N;i++){
num+=i--query(a[i]);
add(a[i],);
}
printf("%d\n",*(num/)+(num&));
return ;
}
上一篇:Raspberry Pi 安装FTP(Pure-FTP)


下一篇:RO05 - 如何编写RemObjects SDK服务端 (Delphi Version)