专栏文章

题解：CF351B Jeff and Furik

hhoko
CF351B题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioztivg
此快照首次捕获于
2025/12/03 03:50
3 个月前
此快照最后确认于
2025/12/03 03:50
3 个月前
查看原文

题目传送门

题意

给定一个排列，有两个人轮流操作，第一个人每次可以减少一个逆序对，第二个人每次有 50%50\% 的概率减少一个逆序对，也有 50%50\% 的概率增加一个逆序对，求让这个序列不含逆序对的最小操作期望。

思路

显然，我们可以列出转移方程：
fi=2+0.5×fi+0.5×fi−2f_i=2+0.5\times f_i+0.5\times f_{i-2}
fif_i 表示含有 ii 个逆序对的最小操作期望。我们把两个人都操作一次设为一组，那么每组操作有 50%50\% 的概率使逆序对数量不变，有 50%50\% 的概率使逆序对的数量减少两个，所以 fi=2+0.5×fi+0.5×fi−2f_i=2+0.5\times f_i+0.5\times f_{i-2}。
最后我们可以用 O(n2)O(n^2) 的复杂度求出有多少逆序对，再 O(1)O(1) 计算即可。设 ansans 为逆序对数，如果 ansans 是偶数，那么答案即为 ans×2ans\times 2，如果是奇数，那么就是 ans÷2×4+1ans\div 2\times 4+1
注意边界条件，f0=0f_0=0，f1=1f_1=1 因为只有一个逆序对时，第一个人可以直接更改，所以只操作一次。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010101;
ll n,a[N],ans,dp[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i]>a[j])ans++;
    cout<<(ans&1)+(ans)/2*4;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...