NextAndPrev

作者：刘子祯 关键词：字符串 贪心 枚举

题目描述

给定一个字符串，然后给定一个目标串，每一次可以讲所有的相同字符+1或者-1，其中z+1=a 给定+1的代价和-1的代价，然后你要计算出最小的代价。

题解

这道题只用很少种状态，可以暴力枚举。 显然，交换字符串的顺序对结果没有影响。 首先枚举分界点，启示的状态有26个分界点，终止的状态也有26个分界点。 这样分界点一共有2626种，根据每一个分界点单独判断情况。 比如分界点为a,那么a就是最小的z就是最大的。 分界点为e，e就是最小，d就是最大。 枚举分界点的就是暴力枚举映射的方向。 假设起点到终点是一个映射，那么需要满足以下条件： 1.不存在一对多的映射2.对于已经排过序的终点状态，起点必须单调不递减。 一对多的映射就是一个起点对应了多个终点，这一定不能实现。 这样，也显然可以看出交叉现象一定是不存在的，因为如果交叉成立，那么走向交叉点的过程中就会发现将不同的字符变成相同的，这时这两个相同的字符就无法分开。 如果满足上面两种情况，则说明这个分界点一定有解，那么对于当前的分界点中只有3种状态可以选择：1.整体向当前最近的位置调节2.整体向下调节3.整体向上调节 分界点的情况一共只有2626种，每一种只有3种状态，并且包含最优状态。 所以一共最多只有26263种状态，也就是说调节的方案最多有26263种，每种状态线性扫一遍，求和判断当前代价，找出最小的即可。 最后就要注意特殊情况： 1.如果起点和重点相同，就是0 2.如果起点和重点不相同并且终点的26种字母都包含，则不成立，因为种情况没有空余的空间，如果调解就变成了25种情况，然后就调不过来了，所以不成立。