蓝桥杯 adv169 士兵排队问题

蓝桥杯 adv169 士兵排队问题

题目描述

有N个士兵(1≤N≤26),编号依次为A,B,C,…,队列训练时,指挥官要把一些士兵从高到矮一次排成一行,但现在指挥官不能直接获得每个人的身高信息,只能获得“P1比P2高”这样的比较结果(P1、P2∈A,B,C,…,Z,记为 P1>P2),如”A>B”表示A比B高。

请编一程序,根据所得到的比较结果求出一种符合条件的排队方案。

(注:比较结果中没有涉及的士兵不参加排队)

输入要求

比较结果从文本文件中读入(文件由键盘输入),每个比较结果在文本文件中占一行。

输出要求

若输入数据无解,打印“No Answer!”信息,否则从高到矮一次输出每一个士兵的编号,中间无分割符,并把结果写入文本文件中,文件由键盘输入:

样例输入

A>B B>D F>D

样例输出

AFBD

参考解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <iostream>
#include <queue>
#include <string>

using namespace std;

int map[30][30], vis[30], deg[30];
string ans;
char u, v;

bool topsort();

int main() {
while (scanf(" %c>%c", &u, &v) != EOF) {
if (map[u-'A'][v-'A']) continue; // 重复输入
map[u-'A'][v-'A'] = 1; // v 在 u 的后面
vis[u-'A'] = vis[v-'A'] = 1; // 涉及到的士兵
++deg[v-'A']; // 矮度 + 1
}
if (topsort()) // 若拓扑排序成功
cout << ans << endl;
else
cout << "No Answer!\n";
return 0;
}

bool topsort() {
int cnt = 0, t = 0;
queue<int> q;
for (int i = 0; i < 30; ++i) {
if (vis[i]) {
++cnt; // 需要排序的个数,即涉及士兵
if (deg[i] == 0)
q.push(i); // 度为 0 的先进队首
}
}

while (!q.empty()) {
int st = q.front();
q.pop();
++t; // 排好一个
ans += st + 'A'; // 输入串

for (int i = 0; i < 30; ++i) {
if (vis[i] && map[st][i]) {
// 这个节点的后继结点度数全部 - 1
if (--deg[i] == 0) q.push(i);
}
}
}
// 图中有环,则不相等
return t == cnt;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×