题解 CF1829C Mr. Perfectly Fine

· · 题解

大家好，我是 CQ-C2024 蒟蒻 CJH。

题意

本题有多组数据。

有 n 本书，第 i 本书所花费的阅读时间为 m_i，还会有一个长度为 2 的二进制数 s_i。

如果 s_{i1}=1 表示他学会了技能 1，如果 s_{i2}=1 表示他学会了技能 2。

请你求出能够学会两个技能所花费的最小时间。如果不能学会，请输出 -1。

分析

我们只需要记录能学会的所有状态所花费的最小时间即可。

能够学会两种技能的情况有两种：

  1. 看了一本能学会两种技能的书。
  2. 看了两本分别能学会技能 1 和技能 2 的书。

代码

//the code is from chenjh
#include<cstdio>
inline int min(const int x,const int y){return x<y?x:y;}
void solve(){
    int n;scanf("%d",&n);
    int a[4]={1000000000,1000000000,1000000000,1000000000};//因为取最小值，所以要先把每种状态赋值为最大值。
    char s[5];
    for(int i=1,x,w;i<=n;i++){
        scanf("%d%s",&x,s);
        w=(s[0]=='1')<<1|(s[1]=='1');//将二进制字符串转化为一个数。
        a[w]=min(a[w],x);
    }
    int ans=min(a[1]+a[2],a[3]);//两种情况的最小值。
    printf("%d\n",ans>=1000000000?-1:ans);//答案超过最大值即没有能学会两种技能的方案。
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}