codeforces 501 B. Obtaining the String

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

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

思路:

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

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

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

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

2 评论 在 "codeforces 501 B. Obtaining the String"

提醒
排序:   最新 | 最旧 | 得票最多

kk居然十一都在刷题orz

wpDiscuz