2017南宁网络赛 Problem J Minimum Distance in a Star Graph ( 模拟 )

72 阅读 0 评论 48 点赞

我是靠谱客的博主大意嚓茶，最近开发中收集的这篇文章主要介绍2017南宁网络赛 Problem J Minimum Distance in a Star Graph ( 模拟 )，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意 : 乱七八糟说了一大堆，实际上就是问你从一个序列到另个序列最少经过多少步的变化，每一次变化只能取序列的任意一个元素去和首元素互换

分析 : 由于只能和第一个元素去互换这种操作，所以没啥最优的特别方法，只要乖乖模拟即可，如果第一个元素不在正确位置则将它和正确位置的元素交换使其回到正确位置，如果第一个元素的位置就是正确的，那么就往后找不在正确位置的元素将它互换到第一个去，然后再对第一个元素进行判断即可，直到序列变成最终满足条件的序列........

#include<bits/stdc++.h>
using namespace std;
map<char, int> pos;
char st[11], en[11];
int n;
bool OK()
{
for(int i=0; i<n; i++){
if(st[i] != en[i])
return false;
}return true;
}
int main(void)
{
scanf("%d", &n);
for(int t=1; t<=5; t++){
pos.clear();
scanf("%s %s", st, en);
for(int i=0; i<n; i++){
pos[en[i]] = i;///记录每一个数字的正确位置

}
int ans = 0;
int p = 0;
while(!OK()){///每一次检查一下序列是否已经变成了最终序列
if(en[0] != st[0]){
swap(st[0], st[pos[st[0]]]);
ans++;
}else{
for(int i=1; i<n; i++){
if(en[i] != st[i]){
swap(st[0], st[i]);
ans++;
break;
}
}
}
}
printf("%dn", ans);
}
return 0;
}