Codeforces1042B. Vitamins(二进制)

题目链接:codeforces1042B. Vitamins

题意:给定 n 个物品,每个物品有一个价格,并且其含有一定的维生素(A,B,C),问在补充所有维生素的情况下的最小消费。

题解:

​ 利用二进制和位运算(与)的思维。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n;
vector<int> a[10];
ll b[10];
int main()
{
    cin>>n;
    for(int i=1;    i<=n;   i++)
    {
        int temp,numa,numb,numc,id;
        numa=numb=numc=id=0;
        string str;
        cin>>temp>>str;
        for(int j=0;    j<str.length(); j++)
        {
            if(str[j]=='A')
                numa=1;
            if(str[j]=='B')
                numb=1;
            if(str[j]=='C')
                numc=1;
        }
        id=numa*4+numb*2+numc;
        a[id].push_back(temp);
    }
    for(int i=1;    i<=7;    i++)
    {
        sort(a[i].begin(),a[i].end());
        if(!a[i].empty())
            b[i]=1ll*a[i][0];
        else
            b[i]=inf;
    }
    ll ans=inf;
    for(int i=1;    i<=7;   i++)
    {
        if(i==7&&b[i]!=inf)
            ans=min(ans,b[i]);
        for(int j=i+1;  j<=7;   j++)
        {
            if((i|j)==7)
            {
                if(b[i]!=inf&&b[j]!=inf)
                    ans=min(ans,b[i]+b[j]);
                continue;
            }
            for(int k=j+1;  k<=7;   k++)
            {
                if((i|j|k)==7)
                {
                    if(b[i]!=inf&&b[j]!=inf&&b[k]!=inf)
                        ans=min(ans,b[i]+b[j]+b[k]);
                }
            }
        }
    }
    if(ans!=inf)
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。