洛谷题解 CF910C 【Minimum Sum】

当时看到这题一脸懵逼，莫名想到了复杂度为O(10000000000*n)的算法，然而肯定会超时(废话)

算法楼上楼下都说的很清楚了

很明显这题是要用每个字母的权值进行排序。然后依次进行赋值。

\(\color{red}\text{注意:不能有前导零，所以要进行特判}\)

看代码吧:

#include<bits/stdc++.h>

using namespace std;

string s[1100];

int n;

struct Node

{

    int num,sum;//num表示该数组下标表示的字母，因为排序后会打乱，所以要先记录一下

    bool first;//是否首字母

}word[11];//分别表示a,b,c,d,e,f,g,h,i,j

int p[11];//表示a~j分别代表的

bool vis[11];//表示0~9这9个数是否用过

inline bool cmp(Node u,Node v)//按权值排序

{

    return u.sum>v.sum;

}

int main()

{

    ios::sync_with_stdio(false);

    cin>>n;

    for(int i=1;i<=10;i++)word[i].num=i;//先赋值

    for(int i=1;i<=n;i++)

    {

        cin>>s[i];

        word[s[i][0]-'a'+1].first=1;//首字母

        for(int j=0;j<s[i].size();j++)

        {

            word[s[i][j]-'a'+1].sum+=pow(10,s[i].size()-j);//加权值

        }

    }

    sort(word+1,word+11,cmp);//排序

    /*for(int i=1;i<=10;i++)

    {

        cout<<word[i].num<<" "<<word[i].sum<<" "<<word[i].first<<endl;

    }*/

    for(int i=1;i<=10;i++)

    {

        if(word[i].first)//如果它是首字母

        {

            for(int j=1;j<=9;j++)if(!vis[j])//从1~9中选一个

            {

                vis[j]=1;//标记为用过

                p[word[i].num]=j;//这时记录的东西就很有用了

                break;

            }

        }

        else

        {

            for(int j=0;j<=9;j++)if(!vis[j])//如果不是首字母，那就在0~9中选择

            {

                vis[j]=1;//标记为用过

                p[word[i].num]=j;

                break;

            }

        }

    }

    /*for(int i=1;i<=10;i++)cout<<p[i]<<" ";

    cout<<endl;*/

    int ans=0;

    for(int i=1;i<=n;i++)

    {

        int cnt=0;

        for(int j=0;j<s[i].size();j++)

        {

            cnt=cnt*10+p[s[i][j]-'a'+1];//计算当前字符串的值

        }

        ans+=cnt;//总答案加上

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

洛谷题解 CF910C 【Minimum Sum】

最新文章

热门文章

巴特西

洛谷 题解 CF910C 【Minimum Sum】

最新文章

热门文章

洛谷题解 CF910C 【Minimum Sum】