首页 > 技术文章 > 水题但仍需细心

LandingGuy 2018-09-21 21:47 原文

cf  B. Vitamins      http://codeforces.com/problemset/problem/1042/B

就是找出果汁组合凑齐ABC 使得果汁价钱最小

#include <iostream>
#include <stdio.h>
#define INF 0xfffffff
using namespace std;
//首先INF 0xffffffff 是-1
//其次后面涉及到最大值的加法,所以INF不能这么大
//在开始时只想到AB+C 没想到AB+BC 
int main()
{
    //cout << "Hello world!" << endl;
    int num,price;
    string type;
    int ch[9];
    while(scanf("%d",&num)!=EOF)
    {
        for(int i=0;i<7;i++)
        {
            ch[i]=-1;
        }
        for(int i=0;i<num;i++)
        {
            cin>>price>>type;
            if(type.size()==1)
            {
                if(ch[type[0]-'A']==-1)  ch[type[0]-'A']=price;
                else ch[type[0]-'A']=min(ch[type[0]-'A'],price);
            }
            else if(type.size()==2)
            {
                if(type=="AB"||type=="BA")
                {
                    if(ch[3]==-1)  ch[3]=price;
                    else ch[3]=min(ch[3],price);
                }
                else if(type=="AC"||type=="CA")
                {
                    if(ch[4]==-1)  ch[4]=price;
                    else ch[4]=min(ch[4],price);
                }
                else
                {
                    if(ch[5]==-1)  ch[5]=price;
                    else ch[5]=min(ch[5],price);
                }
            }
            else
            {
                if(ch[6]==-1)  ch[6]=price;
                    else
                ch[6]=min(ch[6],price);
            }

        }
        for(int i=0;i<7;i++)
        {
            if(ch[i]==-1)
            {
                ch[i]=INF;
            }
        }
        int Min=ch[0]+ch[1]+ch[2];

        Min=min(Min,ch[3]+ch[2]);

        Min=min(Min,ch[4]+ch[1]);

        Min=min(Min,ch[5]+ch[0]);

        Min=min(Min,ch[6]);

        Min=min(Min,ch[3]+ch[4]);

         Min=min(Min,ch[3]+ch[5]);

         Min=min(Min,ch[5]+ch[4]);

        if(Min==INF)
            cout<<-1<<endl;
        else cout<<Min<<endl;


    }
    return 0;
}

 

推荐阅读