题解：P9363 [ICPC 2022 Xi'an R] Hotel

Ethan_sun · 2025-12-17 22:55:27 · 题解

P9363 [ICPC 2022 Xi'an R] Hotel

• update on 2025.12.17 修改原题解的笔误，重新建了一篇文章。

solution

对于这个问题可以分为几种类别求解：

::::info[第一种]{open}

当 2 \times c_1 < c_2 时，开两间单人房的价钱比开一间双人房的价钱还要低，故答案就是全选单人房，即为 3 \times n \times c_1。

::::

::::info[第二种]{open} 当在一个队伍中有性别相同的人时，为性别相同的两人开一间单人房，另一个人自己住在 c_1 与 c_2 中最便宜的那个，所以此时的答案为 c_2 + \min(c_1, c_2)。 ::::

::::info[第三种]{open} 当在一个队伍中没有性别相同的人时，只能安排 3 间 c_1 与 c_2 中最便宜的，故答案就是 3 \times \min(c_1, c_2)。 ::::

code

#include <bits/stdc++.h>
#define int long long
#define maxn 100010
#define endl '\n'
using namespace std;

string s;
int n, ans, c1, c2;
signed main() {
    cin >> n >> c1 >> c2;
    if (2 * c1 < c2) {
        cout << 3 * n * c1 << endl;
        exit(0);
    }
    for (int i = 1; i <= n; i++) {
        cin >> s;
        bool f = false;
        for (int j = 0; j < 3; j++) {
            if (f) {
                break;
            }
            for (int k = 0; k < 3; k++) {
                if (j != k && s[j] == s[k]) {
                    ans += c2 + min(c1, c2);
                    f = true;
                    break;
                }
            }
        }
        if (!f) {
            ans += 3 * min(c1, c2);
        }
    }
    cout << ans << endl;
    return 0;
}