526互联

Educational Codeforces Round 96 (Rated for Div. 2)E

发布时间 2023-07-11 11:47:31作者: 清初

You are given a string s. You have to reverse it — that is, the first letter should become equal to the last letter before the reversal, the second letter should become equal to the second-to-last letter before the reversal — and so on. For example, if your goal is to reverse the string "abddea", you should get the string "aeddba". To accomplish your goal, you can swap the neighboring elements of the string.

Your task is to calculate the minimum number of swaps you have to perform to reverse the given string.

题意：
给您一个字符串s。您必须将其倒转，即第一个字母应等于倒转前的最后一个字母，第二个字母应等于倒转前的倒数第二个字母，以此类推。例如，如果您的目标是将字符串 "abddea "颠倒过来，您应该得到字符串 "aeddba"。为了达到目的，您可以交换字符串中相邻的元素。

您的任务是计算反转给定字符串所需的最少交换次数。

思路：两个相邻的交换次数，类似于冒泡排序，而冒泡排序有一个特点就是交换次数==逆序对数
因为下标是确定的，所以我们可以先把下标求出来，就是看颠倒后和原字符串相比需要变换的位置，然后在按相同字符小的排序，再用树状数组求逆序对就可以了

代码

点击查看代码 
// Problem: E. String Reversal
// Contest: Codeforces - Educational Codeforces Round 96 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1430/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;
#define int long long 

const int N = 1e6 + 10;
int n,m;
int a[N],b[N];
int c[N];
int lowbit(int x)
{
	return x&(-x);
}
void add(int x)
{
	for(;x<=N;)
	{
		c[x] += 1;
		x += lowbit(x);
	}
}
signed query(int x)
{
	int ans = 0;
	for(;x>=1;)
	{
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}
set<int>se[N];
int d[N];
void solve()
{
	cin >> n;
	string s;
	cin >> s;
	for(int i = 1;i <= n;i ++)
	a[i] = i;
	for(int i = 0,j = n-1;i < s.size();i ++,j--)
	{
		if(s[i] == s[j])
		{
			b[i+1] = i+1;
		}
		else
		b[i+1] = j+1;
	}
	for(int i = 1;i <= n;i ++)
	{
		se[s[b[i]-1]].insert(b[i]);
	}
	for(int i = 1;i <= n;i ++)
	{
		//cout << *se[s[b[i]-1]].begin() << '\n';
		d[i] = *se[s[b[i]-1]].begin();
		se[s[b[i]-1]].erase(d[i]);
	}
	// for(int i = 1;i <= n;i ++)
	// {
		// cout << d[i] << " \n"[i == n];
	// }
	for(int i = 1;i <= n;i ++)
	{
		d[i] = n-d[i]+1;
	}
	int cnt = 0;
	for(int i = 1;i <= n;i ++)
	{
		cnt += query(d[i]);
		add(d[i]);
	}
	cout << cnt << '\n';
}
signed main()
{
	int tt = 1;
	while(tt--)
	{
		solve();
	}
}