算法提高 判断名次

问题描述

　　某场比赛过后，你想要知道A~E五个人的排名是什么，于是要求他们每个人说了一句话。（经典的开头……-_-!）得了第1名的人23，说了假话；得了第5名的人不好意思，也说了假话；为了使求解问题简单，第3名同样说了假话。（奇数名次说假话）

输入格式

　　共5行，各行依次表示A~E说的话。

　　每行包含一个形如“A>=3”的名次判断，即一个大写字母+关系运算符+一个数字，不包含空格。

　　大写字母A~E，关系运算<、<=、=、>=、>、!=，数字1~5。注意：等于是“=”不是“==”！

输出格式

　　可能有多解，请按照字典序输出排名序列，每个解一行

　　最后一行输出解的数量

样例输入

A=2

D=5

E>3

A>2

B!=1

样例输出

ACDEB

AECBD

BADCE

BCADE

BDACE

CEADB

CEBDA

7

问题分析

答案要求按字典序输出，如果用全排列函数来做，那么可以省去排序的过程。所有的排列只有5！种，因此时间可控。

1.检测每一种可能的排序

2.如果奇数名次的人说了真话，那么此排列不可取

3.如果偶数名次的人说了假话，那么此排列不可取

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
using namespace std;
string words[5];
string ord = "ABCDE";
int sum = 0;
bool isright() {
	int h[150];
	for (int i = 0; i < 5; i++) {
		h[ord[i]] = i + 1;
	}
	for (int i = 0; i < 5; i++) {//处理每个人讲的话
		int len = words[i].length();
		if (h['A' + i] % 2 == 1) {//名次为奇数 说假话
			if (words[i][1] == '=' && h[words[i][0]] == words[i][len - 1] - '0')	return false;
			if (words[i][1] == '!' && h[words[i][0]] != words[i][len - 1] - '0')	return false;
			if (len == 3 && words[i][1] == '<' && h[words[i][0]] < words[i][len - 1] - '0')	return false;
			if (len == 3 && words[i][1] == '>' && h[words[i][0]] > words[i][len - 1] - '0')	return false;
			if (len == 4 && words[i][1] == '>' && h[words[i][0]] >= words[i][len - 1] - '0')	return false;
			if (len == 4 && words[i][1] == '<' && h[words[i][0]] <= words[i][len - 1] - '0')	return false;
		}
		else {//名次偶数 说真话
			if (words[i][1] == '=' && h[words[i][0]] != words[i][len - 1] - '0')	return false;
			if (words[i][1] == '!' && h[words[i][0]] == words[i][len - 1] - '0')	return false;
			if (len == 3 && words[i][1] == '<' && h[words[i][0]] >= words[i][len - 1] - '0')	return false;
			if (len == 3 && words[i][1] == '>' && h[words[i][0]] <= words[i][len - 1] - '0')	return false;
			if (len == 4 && words[i][1] == '>' && h[words[i][0]] < words[i][len - 1] - '0')	return false;
			if (len == 4 && words[i][1] == '<' && h[words[i][0]] > words[i][len - 1] - '0')	return false;
		}
	}
	sum++;
	return true;
}
int main() {
	for (int i = 0; i < 5; i++) {
		cin >> words[i];
	}
	do {
		if (isright())
			cout << ord << endl;
	} while (next_permutation(ord.begin(), ord.end()));
	cout << sum;
	return 0;
}

参考分析