codeforces 501 B. Obtaining the String

2018年10月3日 2 作者 CrazyKK

题目链接:http://codeforces.com/contest/1015/problem/B

题意: 给出字符串s和字符串t,问一个将s变为t的策略。 可以做的变换为,交换s中相邻的字符串,该操作最多不能超过4000次,字符串长度最大为50.

思路:

首先可以确定,当两个字符串的组成相同时(也就是有同样的字符组成,只是位置可能有所不同)一定有解。

考虑最坏情况,每个字符都要交换到最远的地方,总的操作数<50*50<4000,因此一定有解。

判断组成是否相同可以用multiset