阿里春招笔试2020.3.27(贪心/差分/概率)

申明:大概题意是从牛客网讨论区嫖的，题目的输入、输出以及数据数据范围也有些不知，大家看看思路就好，这些细节就不管了QAQ。有错欢迎纠正~ 3.27

题目一（贪心）

给定字符串s1,s2，求从s1变为s2的最小移动次数（要求每一次只能从s1选取任意一个字符放到s1最后） 思路：贪心。首先如果两个字符串对应的字符数不匹配的话，那么答案一定是-1。否则的话，我们一定可以构造新的s，使得和t相等。由于s的字符可以移动，而t的字符不能移动。所以该本质是求s的最长不连续子串，使得和t的前缀子串匹配。由于是匹配t的前缀子串，那么我们可以贪心的匹配即可，每遇到一个s的字符和t的当前字符匹配，则t的字符向前移动一位。最终答案就是n-可以匹配 的最多位数。

#include
using namespace std;
const int maxn = 100010;

char s[maxn],t[maxn];
int mp1[27],mp2[27];//统计各个字符数 
int n;
int main() {
	scanf("%d",&n);
	scanf("%s%s",s,t);
	int j = 0;
	for(int i = 0;i