集美大学第九届程序设计竞赛 L.序列 逆序对

集美大学第九届程序设计竞赛 L.序列 逆序对计数

链接：https://ac.nowcoder.com/acm/contest/42400/L

题目思路

要求最小交换次数使得序列变为单峰序列。

首先有一个很显然的选择问题：每个数字$a[i]$一定有两种选择：

• 交换到某个最左侧的位置$pos$，使得$\forall j\in [1,pos],a[j]\le a[i]$；
• 交换到某个最右侧的位置$pos$，使得$\forall j\in [pos+1],a[j]\ge a[i]$；

那么我们从前到后进行遍历，对于每个数字进行暴力交换求最小操作数，然后发现过于暴力。

那么考虑如何快速计数：我们发现如果按照顺序对每个元素进行决策，那么对于一个数，如果选择策略1(换到最左侧)，那么它需要交换的次数等于左边比他大的数的个数。因为按照遍历顺序进行决策，前序的数字一定已经交换到了合法的位置，从而不会有谷形状(感性理解)的出现。

那么直接逆序对计数正反统计两遍计算交换次数，对每个数字取两个决策的最小交换次数即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;
int a[N];

namespace Fenwick{
    int tree[N], len;
    #define lowbit(x) ((x) & (-x))
    inline void update(int i, int x){
        for(int pos = i; pos <= len; pos += lowbit(pos)) tree[pos] += x;
    }

    inline int getsum(int i, int ans = 0){
        for(int pos = i; pos; pos -= lowbit(pos)) ans += tree[pos];
        return ans;
    }

    inline int query(int l, int r){ return getsum(r) - getsum(l - 1); }
}

int l[N], r[N];

inline void solve(){
    int n = 0; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    Fenwick::len = n;
    for(int i = 1; i <= n; i++) l[i] = i - 1 - Fenwick::getsum(a[i]), Fenwick::update(a[i], 1);
    memset(Fenwick::tree, 0, sizeof Fenwick::tree);
    for(int i = n; i >= 1; i--) r[i] = n - i - Fenwick::getsum(a[i]), Fenwick::update(a[i], 1);
    int ans = 0;
    for(int i = 1; i <= n; i++) ans += min(l[i], r[i]);
    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46