---

游游的字母串 （环形数组两点之间的位置）

原创 于 2023-10-15 21:02:22 发布 · 粉丝可见 · 403 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/133847415

题目链接： 登录—专业IT笔试面试备考平台_牛客网

题目：

样例：

undefined<br/>yab<br/>

3

思路：

暴力枚举，全部变成对应的26个字母字符需要的操作步数，取最少的一个操作步数，

这里的操作步数，是 环形 26 字母数组中 两个字符之间最短距离。

环形数组的两个元素之间的最短距离关系是

sql<br/><br/>i j 分别表示两个不同的元素<br/><br/>int dis = min(abs(i - j),环形数组大小 - abs(i - j))<br/>

这里环形数组的大小是 26 。

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define mk make_pair
#define int long long
#define NO puts("NO")
#define YES puts("YES")
#define umap unordered_map
#define INF 0x3f3f3f3f3f3f3f3f
#define All(x) (x).begin(),(x).end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
using PII = pair<int,int>;
inline void solve()
{
	string s;
	int ans = INF;	// ans 取正无穷，方便取 min
	cin >> s;
	
	// 遍历 26 个字母
	for(int i = 0;i < 26;++i)
	{
		int tem = 0;	// 临时存储总距离
		// 全部字符变成 对应的字母
		for(char j : s)
		{
            int c = j - 'a';    // 对应字母
			int mid = abs(i - c);	// 中间的距离
			int out = 26 - abs(i - c);	// 全部距离 - 中间距离 == 外边距离
			int dis = min(mid,out);
			tem += dis;
		}
		ans = min(ans,tem);	// 取最少总距离，即最少操作数
	}
	cout << ans << endl;
}
signed main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：