神奇的椅子

编程入门行业动态更新时间:2024-10-26 08:20:57

神奇的<a href=https://www.elefans.com/category/jswz/34/1741032.html style= 椅子"/>

神奇的椅子

题目较长，直接上图

思路：暴力枚举，也就是深度搜索，搜索出所有可能的组合，然和计算该组合的分数：

首先是深度搜索进行枚举

假设我们男人，女人，孩子的人数分别为1，1，1 。我们就安排三个座位，第一个座位可以安排男人，女人，或者孩子，后面两个座位类似安排，这就是枚举，同时注意一些条件，比如男人不能坐在孩子前面，枚举时注意去掉这些，这就是剪枝。

#include <iostream>
#include <string>
using namespace std;
string ans;//用来存储每个位置放入的人,下标相当于座位号，我们从1号座位开始安排
//可以把ans改为sit便于理解
int m,w,c,total;//分别表示男人，女人，孩子和总人数
void display() {//打印ans，我们从下标1开始安排，所以从下标1开始打印for (int i = 1; i <total; i++) {cout << ans[i] << "->";}cout << ans[total];cout << endl;
}
void dfs(int index,int m,int w,int c) {//深度优先搜索，参数依次为，安排第index位置，后面依次为剩余男人，女人，小孩的人数if (index==total+1) {//边界条件，也就是所有人数都安置完了display();return;}if (c > 0 && ans[index - 1] != 'M') {//这里有个剪枝：当前面一个位置是男人时，后面不允许是小孩ans.push_back('C');//放置小孩dfs(index + 1, m, w, c - 1);//进入下一步搜索，索搜index+1位置，同时孩子的人数-1ans.pop_back();//回溯}if (w > 0 ) {ans.push_back('W');//放置女人dfs(index + 1, m, w - 1, c);ans.pop_back();}if (m > 0) {ans.push_back('M');//放置男人dfs(index + 1, m - 1, w, c);ans.pop_back();}
}
int main() {while (cin >> m >> w >> c) {total = m + w + c;ans.clear();ans.push_back('0');//我们从下标1开始放置，所以在下标0处随便填充一个字符dfs(1, m, w, c);//从1处开始搜索}
}

运行结果：

1 1 1
C->W->M
C->M->W
W->C->M
M->W->C

可以看到，我们枚举出4种所有的可能，仔细一看，还是有些问题，第一种是不允许的，因为我们用的是一个线性结构，而题目是一个环形，最后一个男人相当于坐在了第一个男人前面。我们在后面计分的时候把这种情况记为0分就行。

如何计分呢，很简单，遍历搜索就完事了，先搜有没有家庭组合，再搜有没有父子组合，然后母子组合，注意：家庭组合包含了母子组合，最后搜有没有扣分的情况。

double grade(const string &s) {double sum = m * 2 + w * 1 + c*0.5;int n1 = 0, n2 = 0; //n1表示家庭组合数，n2表示母子组合数if (s[1] == 'C'&& s[total] == 'M')//前面说过这种情况，记为0分return 0;else {//搜索家庭组合for (int i = 1; i <= total - 2; i++) {if (s[i] == 'C'&&s[i + 1] == 'W'&&s[i + 2] == 'M') {sum += 3;n1++;}}//注意题目是环形，所以我们还要搜索下面两种，后面的情况类似处理if (s[total - 1] == 'C'&&s[total] == 'W'&&s[1] == 'M') {sum += 3;n1++;}if (s[total] == 'C'&&s[1] == 'W'&&s[2] == 'M') {sum += 3;n1++;}//搜索父子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'M')sum += 2.5;if (s[total] == 'C'&&s[1] == 'M')sum += 2.5;//索搜母子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'W')n2++;if (s[total] == 'C'&&s[1] == 'W')n2++;sum += (n2 - n1) * 2;//家庭组合包含了母子组合，不能重复计分//搜索扣分的情况for (int i = 1; i <= total - 1; i++)if (s[i] == 'M'&&s[i + 1] == 'W')sum--;if (s[total] == 'M'&&s[1] == 'W')sum--;}return sum;//返回
}

然后把上面两个整合下；

#include <iostream>
#include <string>
using namespace std;
string ans;//用来存储每个位置放入的人
int m, w, c, total;//分别表示男人，女人，孩子和总人数
void display() {//打印ans，我们从下标1开始存，所以从下标1开始打印for (int i = 1; i <total; i++) {cout << ans[i] << "->";}cout << ans[total];cout << endl;
}
double grade(const string &s) {double sum = m * 2 + w * 1 + c*0.5;int n1 = 0, n2 = 0; //n1表示家庭组合数，n2表示母子组合数if (s[1] == 'C'&& s[total] == 'M')//前面说过这种情况，记为0分return 0;else {//搜索家庭组合for (int i = 1; i <= total - 2; i++) {if (s[i] == 'C'&&s[i + 1] == 'W'&&s[i + 2] == 'M') {sum += 3;n1++;}}//注意题目是环形，所以我们还要搜索下面两种，后面的情况类似处理if (s[total - 1] == 'C'&&s[total] == 'W'&&s[1] == 'M') {sum += 3;n1++;}if (s[total] == 'C'&&s[1] == 'W'&&s[2] == 'M') {sum += 3;n1++;}//搜索父子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'M')sum += 2.5;if (s[total] == 'C'&&s[1] == 'M')sum += 2.5;//索搜母子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'W')n2++;if (s[total] == 'C'&&s[1] == 'W')n2++;sum += (n2 - n1) * 2;//家庭组合包含了母子组合，不能重复计分//搜索扣分的情况for (int i = 1; i <= total - 1; i++)if (s[i] == 'M'&&s[i + 1] == 'W')sum--;if (s[total] == 'M'&&s[1] == 'W')sum--;}return sum;//返回
}
void dfs(int index, int m, int w, int c) {//深度优先搜索，参数依次为，安排第index位置，后面依次为剩余男人，女人，小孩的人数if (index == total + 1) {//边界条件，也就是所有人数都安置完了display();cout << "该组合的分数为：" << grade(ans) << endl;return;}if (c > 0 && ans[index - 1] != 'M') {//这里有个剪枝：当前面一个位置是男人时，后面不允许是小孩ans.push_back('C');//放置小孩dfs(index + 1, m, w, c - 1);//进入下一步搜索，索搜index+1位置，同时孩子的人数-1ans.pop_back();//回溯}if (w > 0) {ans.push_back('W');//放置女人dfs(index + 1, m, w - 1, c);ans.pop_back();}if (m > 0) {ans.push_back('M');//放置男人dfs(index + 1, m - 1, w, c);ans.pop_back();}
}
int main() {while (cin >> m >> w >> c) {total = m + w + c;ans.clear();ans.push_back('0');//我们从下标1开始放置，所以在下标0处随便填充一个字符dfs(1, m, w, c);//从1处开始搜索}
}

运行结果：

0 1 1
C->W
该组合的分数为：3.5
W->C
该组合的分数为：3.5
1 0 1
C->M
该组合的分数为：0
1 1 1
C->W->M
该组合的分数为：0
C->M->W
该组合的分数为：5
W->C->M
该组合的分数为：5
M->W->C
该组合的分数为：5

最后整理为题目的答案：

#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
string ans;//用来存储每个位置放入的人
int m, w, c, total;//分别表示男人，女人，孩子和总人数
double score;//保存分数
void display() {//打印ans，我们从下标1开始存，所以从下标1开始打印for (int i = 1; i <total; i++) {cout << ans[i] << "->";}cout << ans[total];cout << endl;
}
double grade(const string &s) {double sum = m * 2 + w * 1 + c*0.5;int n1 = 0, n2 = 0; //n1表示家庭组合数，n2表示母子组合数if (s[1] == 'C'&& s[total] == 'M')//前面说过这种情况，记为0分return 0;else {//搜索家庭组合for (int i = 1; i <= total - 2; i++) {if (s[i] == 'C'&&s[i + 1] == 'W'&&s[i + 2] == 'M') {sum += 3;n1++;}}//注意题目是环形，所以我们搜索下面两种，后面的情况类似处理if (s[total - 1] == 'C'&&s[total] == 'W'&&s[1] == 'M') {sum += 3;n1++;}if (s[total] == 'C'&&s[1] == 'W'&&s[2] == 'M') {sum += 3;n1++;}//搜索父子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'M')sum += 2.5;if (s[total] == 'C'&&s[1] == 'M')sum += 2.5;//索搜母子组合for (int i = 1; i <= total - 1; i++)if (s[i] == 'C'&&s[i + 1] == 'W')n2++;if (s[total] == 'C'&&s[1] == 'W')n2++;sum += (n2 - n1) * 2;//家庭组合包含了母子组合，不能重复计分//搜索扣分的情况for (int i = 1; i <= total - 1; i++)if (s[i] == 'M'&&s[i + 1] == 'W')sum--;if (s[total] == 'M'&&s[1] == 'W')sum--;}return sum;//返回
}
void dfs(int index, int m, int w, int c) {//深度优先搜索，参数依次为，安排第index位置，后面依次为剩余男人，女人，小孩的人数if (index == total + 1) {//边界条件，也就是所有人数都安置完了score = max(score, grade(ans));return;}if (c > 0 && ans[index - 1] != 'M') {//这里有个剪枝：当前面一个位置是男人时，后面不允许是小孩ans.push_back('C');//放置小孩dfs(index + 1, m, w, c - 1);//进入下一步搜索，索搜index+1位置，同时孩子的人数-1ans.pop_back();//回溯}if (w > 0) {ans.push_back('W');//放置女人dfs(index + 1, m, w - 1, c);ans.pop_back();}if (m > 0) {ans.push_back('M');//放置男人dfs(index + 1, m - 1, w, c);ans.pop_back();}
}
int main() {while (cin >> m >> w >> c) {total = m + w + c;ans.clear();//初始化score = 0;//初始化ans.push_back('0');//我们从下标1开始放置，所以在下标0处随便填充一个字符dfs(1, m, w, c);//从1处开始搜索cout << fixed << setprecision(1) << score << endl;}
}

运行结果：