DDOSvoid's Blog

CF 1430C String Reversal

发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/1430/problem/E

给定一个字符串 $s$，要求只能每次交换 $s$ 的相邻两位，求最少需要交换多少次才能使得 $s$ 变成 $reverse(s)$

Solution

首先有一个简单的贪心，在 $s$ 中的第一个字符 $c$，在 $reverse(s)$ 中也是第一位

然后我们参考逆序对的数量等于交换相邻两个数使得数列变的有序的次数

我们令 $p_i$ 表示 $s$ 中 $i$ 位置的字符应该到的位置

然后求这个东西的逆序对就行

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define maxn 200010
#define pb push_back
#define lowbit(i) ((i) & (-i))
#define ll long long 
using namespace std;

int n;

char s[maxn]; 

vector<int> A[26], B[26]; 

int a[maxn]; 

int Bit[maxn];
inline void add(int i, int v) { while (i <= n) Bit[i] += v, i += lowbit(i); }

inline int get_sum(int i) {
    int s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s;
} 

int main() {
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; ++i) A[s[i] - 'a'].pb(i), B[s[i] - 'a'].pb(n - i + 1);
    for (int i = 0; i < 26; ++i) sort(B[i].begin(), B[i].end());
    for (int i = 0; i < 26; ++i) {
        int l = A[i].size();
        for (int j = 0; j < l; ++j) a[A[i][j]] = B[i][j];
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += i - 1 - get_sum(a[i] - 1);
        add(a[i], 1);
    } cout << ans << endl; 
    return 0;
}