【算法】期末复盘，酒店住宿问题——勿向思想僵化前进

前言

省流：一个人也可以住双人间，如果便宜的话。

害！尚正值青春年华，黄金岁月，小脑瓜子就已经不灵光咯。好在我在考试的最后一分钟还是成功通过了这题，真刺激。

题目描述

一共有 n 个小队，每个小队有 3 个队员，每个队员有一个号码 x 。酒店有单人间和双人间两种，其中单人间一晚上 a 元，双人间一晚上 b 元。为了避免尴尬，只有同属一个小队且号码相同的两个队员，才可以一起住双人间（不要纠结为什么号码相同就不会尴尬）。
问：将n个小队的所有队员全部安排好房间，最少需要花费多少元？

输入描述：
第一行三个整数：n, a, b。然后有 n 行，每行有三个整数，分别是一个小队中三个队员的号码。
其中 1 <= n, a, b <= 100，0 <= x（号码） <= 10。

卡在哪里

这题看起来就简单，我起初的思路是，根据一个双人间是否比两个单人间要便宜，分两种情况：

1. 一个双人间更便宜。那么，当一个小队三人中存在某两人编号相同，就给他们开一个双人间，剩下一个人开单人间；这个小队的花费就是$a+b$。
2. 两个单人间更便宜。那么，不管编号是否有相同，咱都住单人间就好了。

看似好像没啥bug，但有个神奇的问题，双人间一定要两个人才可以住吗？如果$b<a$，那么一个人睡单人间是睡，一个人睡双人间也是睡，一个人也不会存在尴尬的问题，还便宜。

代码（C++）

#include<iostream>
using namespace std;
int main(void){int n, a, b;  //人数，单人间价格，双人间价格cin >> n >> a >> b;int count(0); // 花费for(int i = 0; i < n; i++){int x, y, z;  // 三个队员的号码cin >> x >> y >> z;// 1. 双人间太贵if(a * 2 < b){count += a * 3;}// 2. 双人间比两个单人间便宜else if(a < b && b <= a * 2){if(x == y || x == z || y == z){count += a + b;}else{count += a * 3;}}// 3. 双人间比一个单人间还便宜else{if(x == y || x == z || y == z){count += b * 2;}else{count += b * 3;}}}cout << count;return 0;
}

---