P2133 天作之合
题目背景
生活就是一次 A*，你是我的第一个目标状态。——小明
题目描述
在小明的学校中，有若干个女生。小明认为每个女生的特征可以抽象为一个666位的数字串，其中不重复地包含1∼61\sim61∼6这666个数码。
在小明心中，有一个理想的女生，她的特征数字串为AAA。如果串YYY是串XXX交换两个连续的数码所得，那么我们认为特征数字串XXX和YYY相似。首先，小明找到了他的同桌，她的特征数字串为SSS。每次，小明会寻找一个特征数字串和当前串相似的女生，直到寻找到适合他的（即特征数字串和AAA相同或相似的）。定义每个女生的合适程度为找到此人至少需要找女生的数量（包括他的同桌和此人自己）。显然，合适程度数值越小的女生越适合小明。
然而，小明觉得老天不会轻易地让他找到，所以他认为合适程度第二小的才是他最合适的伴侣（也就是小红）。那么，请你帮他写一个程序，求出对于小明，小红的合适程度是多少。
输入格式
第111行，一个特征数字串AAA。
第222行，一个特征数字串SSS。
输出格式
一行，一个非负整数表示小红的合适程度。
输入输出样例 #1
输入 #1
123654 123456输出 #1
3说明/提示
样例解释：
最短的两个「合适的数字串」分别是454\tt 454454和545\tt 545545，故答案为333。
对于全部数据，保证串AAA和SSS合法，且保证能找到。
C++实现
#include<bits/stdc++.h>usingnamespacestd;string a,b;intdata[10];map<char,int>m;intmain(){cin>>a>>b;a=' '+a;//加上空格，个人习惯使用s[1]~s[6]b=' '+b;intans=0,cnt=0;for(inti=1;i<=6;i++)m[a[i]]=i;//map标记每个数字正确的位置for(inti=1;i<=6;i++)data[i]=m[b[i]];//同上，data[i]为b[i]应该在的位置for(inti=1;i<=6;i++)for(intj=i+1;j<=6;j++)if(data[j]<data[i])ans++;//求逆序对个数if(ans<2)ans+=2;//特判，如果没交换或者只交换了一次，必定属于最优解加2的情况else{for(inti=1;i<=6;i++)if(abs(data[i]-m[a[i]])==ans)cnt++;//特殊情况出现if(cnt==1)ans+=2;//只有一个数在移动}cout<<ans;return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
