String Reversal
题意
对于一个字符串 每次可以交换相邻的两个字符 问 最少经过多少次操作后能将原来的字符串倒序
思路
对于样例 aaaza 倒序后应该是 azaaa 从最后一个字符开始看 需要有一个a 移到最后面，因为源字符串中有多个a 显然 把下标最大的a 移到最后花费的操作次数最小
操作前下标12345 操作后下标14235 逆序数恰好为 2 所以大胆假设 不用求证(不是) 本题即为按照上面规得到新的下标然后求逆序数即可 逆序数用树状数组维护
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define endl '\n' using namespace std; typedef long long LL; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } inline LL lowbit(LL x) {return x & -x;} const int N = 200010; LL n; string s; vector<int>v[30]; int temp[30]; //记录每个字母使用到了第几个 LL tr[4 * N]; LL query(LL x) { LL res = 0; for (int i = x; i ; i -= lowbit(i))res += tr[i]; return res; } void modify(LL x, LL c) { for (int i = x; i <= n; i += lowbit(i))tr[i] += c; } void solve() { cin >> n; cin >> s; for (int i = n - 1; i >= 0; --i) { v[s[i] - 'a'].push_back(i + 1); //存每个字母出现的位置 大的优先 } reverse(s.begin(), s.end()); LL res = 0; for (int i = n - 1; i >= 0; --i) { LL x = query(v[s[i] - 'a'][temp[s[i] - 'a']]); res += x; //cout << "! " << v[s[i] - 'a'][temp[s[i] - 'a']] << endl; //cout << "x == " << x << endl; modify(v[s[i] - 'a'][temp[s[i] - 'a']], 1); temp[s[i] - 'a']++; } cout << res << endl; } int main() { //int t; cin >> t; //while(t--) solve(); return 0; }
