G Swapping Places GYM102501（贪心）

本文主要是介绍G Swapping Places GYM102501（贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

题意：
s种动物，l个朋友关系。n个动物排成一行，相邻为朋友的动物可以交换，求所得最小字典序串。

思路：
因为只有200个位置，那么逐位确定。
假设当前在位置 $i$ ，对所有种类动物进行判断，看这种动物能否交换到位置 $i$ 。
实际就是每种动物遍历了所有位置，复杂度为 n*s。

本题中不能交换的动物相对位置不能改变，貌似能有拓扑排序的解法

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <queue>using namespace std;typedef long long ll;const int maxn = 100005;
const ll INF = 0x3f3f3f3f3f3f3f3f;map<int,string>mp1;
map<string,int>mp2;
int dat[1005][1005];
int cnt;
string num[maxn];
int a[maxn];
int loc[maxn],flag[maxn],vis[maxn],ans[maxn];
int s,l,n;void update() {for(int j = 1;j <= s;j++) {while(vis[loc[j]] || (loc[j] <= n && a[loc[j]] != j && dat[a[loc[j]]][j])) ++loc[j];if(loc[j] <= n && a[loc[j]] == j) flag[j] = 1;}
}int main() {scanf("%d%d%d",&s,&l,&n);for(int i = 1;i <= s;i++) {cin >> num[i];}sort(num + 1,num + 1 + s);for(int i = 1;i <= s;i++) {mp1[i] = num[i];mp2[num[i]] = i;loc[i] = 1;}for(int i = 1;i <= l;i++) {string x,y;cin >> x >> y;int X = mp2[x],Y = mp2[y];dat[X][Y] = dat[Y][X] = 1;}for(int i = 1;i <= n;i++) {string now;cin >> now;a[i] = mp2[now];}for(int i = 1;i <= n;i++) {update();int res = 1;for(int j = 1;j <= s;j++) {if(flag[j]) {res = j;break;}}ans[i] = res;vis[loc[res]] = 1;++loc[res];flag[res] = 0;}for(int i = 1;i <= n;i++) {cout << mp1[ans[i]] << ' ';}return 0;
}