0%

Codeforces 1607A Linear Keyboard

题目大意

给你一个自定义的排成一行的键盘,问你输入一个句子最少需要移动多少次。

分析

我们先来考虑不存在自定义键盘的情况,不妨假设这个键盘正好是 \(\texttt{a}\dots\texttt{z}\)

这时只需要简单的模拟即可,总共的移动距离是每两个键之间距离之和。即 \[ \sum_{i=2}^n{ \left| \operatorname{pos}s_i - \operatorname{pos}s_{i-1}\right|} \] 这时来考虑自定义键盘,可以发现主要的难点在于自定义时 \(\operatorname{pos}\) 的维护。我们可以考虑使用 std::map 来维护。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
std::map<char, int> mp;  // 维护 pos
for (int i = 1; i <= 26; i++) {
char ch;
std::cin >> ch;
mp[ch] = i;
}

int ans = 0;
std::string s;
std::cin >> s;
for (int i = 0; i < s.size() - 1; i++) {
ans += std::abs(mp[s[i]] - mp[s[i + 1]]); // 计算移动距离
}
std::cout << ans << '\n';