CF351B
Description
两个人 A,B,一个长为 \(n\) 的序列,A 每次选两个相邻元素交换,B 有相等的概率把任意满足 \(p_i<p_{i+1}\) 的 \(p_i\) 和 \(p_{i+1}\) 或 \(p_{i}>p_{i+1}\) 的 \(p_{i}\) 和 \(p_{i+1}\) 交换。
求将序列变成升序的最小值期望步数。
Solution
每一次 A 肯定是交换一个逆序对,而 B 每次有 \(50\%\) 的概率减少一个逆序对,有 \(50\%\) 增加一个逆序对,设 \(f_i\) 表示 \(i\) 个逆序对时的最小期望步数,则转移为 \(f_i=\frac{1}{2}(f_{(i-1)-1}+2)+\frac{1}{2}(f_{(i-1)+1}+2)\)
化简一下:
\(f_i=f_{i-2}+4\)
易知 \(f_0=0,f_1=1\) 。
然后我们发现当 $ f_i$ 是偶数的时候,\(f_i=f_{\frac{i}{2}}+4=(f_{\frac{i}{4}}+4)+4=\dots=f_0+4\times\frac{i}{2}=2i\)
当 \(f_i\) 是奇数的时候,\(f_i=f_{\frac{i}{2}}+4=(f_{\frac{i}{4}}+4)+4=\dots=f_1+4\times(\lfloor\frac{i}{2}\rfloor-1)=2i-1\)
然后求一次逆序对个数,根据奇偶性判断就行了。
Code
/* * @Author: smyslenny * @Date: 2021.09.04 * @Title: CF351B Jeff and Furik * @Main idea:求逆序对个数,判断奇偶性,Ans=2*odd-1 || 2*even */ #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <iomanip> #include <cstring> #include <cstdlib> #include <queue> #include <vector> #define ll long long #define INF 0x3f3f3f3f #define orz cout<<"LKP AK IOI\n" #define MAX(a,b) (a)>(b)?(a):(b) #define MIN(a,b) (a)>(b)?(a):(b) #define lowbit(x) (x)&(-x) using namespace std; const int mod=998244353; const int M=3e3+5; int n,Ans; int read() { int x=0,y=1; char c=getchar(); while(c<'0' || c>'9') {if(c=='-') y=0;c=getchar();} while(c>='0' && c<='9') { x=x*10+(c^48);c=getchar();} return y?x:-x; } struct node{ int val,id; }sz[M]; bool cmp(const node &a,const node &b) { return a.val<b.val; } int sum[M]; void add(int x,int k) { for(int i=x;i<=n;i+=lowbit(i)) sum[i]+=k; } int query(int x) { int cnt=0; for(int i=x;i;i-=lowbit(i)) cnt+=sum[i]; return cnt; } int main() { n=read(); for(int i=1;i<=n;i++) sz[i].val=read(),sz[i].id=i; sort(sz+1,sz+1+n,cmp); for(int i=1;i<=n;i++) add(sz[i].id,1),Ans+=(i-query(sz[i].id)); if(Ans&1) printf("%lf\n",(double)2*Ans-1); else printf("%lf\n",(double)2*Ans); return 0; }