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

· · 题解

题面

大意：给定 n 个队伍的队员性别，让你求最小的花费(什么性别 26 个啊)。

前置知识

字符串，一定数学能力。

算法分析

只能同队住房，那就对每个输入进行处理。

首先很容易就能发现有两个显而易见的方案：

取最小值即可。

还有没有其他方案呢？

当然，只要有两人性别相同，我们就可以让他们住进双人间，也就是一单一双的方案。

有人就问了：没有两单一双的方案吗？

双人间只住一人，那么如果双人便宜，我们就该全买单人（方案一）；否则就全买双人（方案二）。所以我们已经处理过了这种情况。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,ans=0,c1,c2;
int main(){
    cin>>n>>c1>>c2;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        int a1=min(c1,c2)*3,a2=0,a3=0;
        if(s[0]==s[1]||s[0]==s[2]||s[1]==s[2]){
            a2=c2+c1;
            a3=c2*2;
            ans+=min(a1,min(a2,a3));
        } 
        else{
            ans+=a1;
        }
    }
    cout<<ans;
    return 0;
}