「Codeforces 351B」Jeff and Furik

发表于 | | 阅读次数:
字数统计: 547 字

Description

题目链接：Codeforces 351B

给出一个长度为 $n$ 的排列 $p_i$，Jeff 和 Furik 会分别轮流进行操作，Jeff 先手。每次操作时，Jeff 会选择相邻的两个数 $p_i,p_{i+1}$ 交换位置；Furik 会抛一枚硬币，如果硬币正面朝上，那么他会随机选择一对 $i$ 和 $i+1$ 且满足 $p_i>p_{i+1}$ 并交换他们；否则他会随机选择一对 $i$ 和 $i+1$ 且满足 $p_i<p_{i+1}$ 并交换他们。当这个序列递增时，游戏结束。假设 Jeff 希望尽快结束游戏（即他希望两人剩余的操作次数最少），求出一共需要的操作次数的期望。

数据范围：$1\le n\le 3000$

Solution

我们对 Jeff 和 Furik 的操作分开考虑：

  • Jeff：每次操作减少 $1$ 个逆序对。
  • Furik：每次操作有 $\frac{1}{2}$ 的概率增加 $1$ 个逆序对，有 $\frac{1}{2}$ 的概率减少 $1$ 个逆序对。

根据期望的可加性，我们可以知道每两次操作，有 $\frac{1}{2}$ 的概率增加 $2$ 的逆序对，有 $\frac{1}{2}$ 的概率逆序对数量不变。因此，每两次操作期望减少 $1$ 个逆序对，答案就是 $2\times\text{逆序对个数}$。

但是如果根据以上思路，我们会发现样例都过不了。其实这里有一些细节问题：需要对逆序对的奇偶性分类讨论！

  • 有奇数个逆序对：那么最后 Jeff 进行操作后序列已经递增。操作次数为 $2\times\text{逆序对个数}-1$。
  • 有偶数个逆序对：没有边界的问题，答案就是 $2\times\text{逆序对个数}$。

时间复杂度：$O(n\log n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <cstdio>

const int N=3005;
int n,a[N],bit[N],cnt;

void add(int x,int val) {
    for(;x<=n;x+=x&-x) bit[x]+=val;
}
int query(int x) {
    int res=0;
    for(;x;x-=x&-x) res+=bit[x];
    return res;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=n;i>=1;--i) {
        cnt+=query(a[i]-1);
        add(a[i],1);
    }
    printf("%d.000000\n",(cnt<<1)-(cnt&1));
    return 0;
}
0%