今日头条笔试题-最大映射(贪心)

Posted by 111qqz on Wednesday, March 29, 2017

TOC

有 n 个字符串,每个字符串都是由 A-J 的大写字符构成。现在你将每个字符映射为一个 0-9 的数字,不同字符映射为不同的数字。这样每个字符串就可以看做一个整数,唯一的要求是这些整数必须是正整数且它们的字符串不能有前导零。现在问你怎样映射字符才能使得这些字符串表示的整数之和最大?
    输入描述:每组测试用例仅包含一组数据,每组数据第一行为一个正整数 n , 接下来有 n 行,每行一个长度不超过 12 且仅包含大写字母 A-J 的字符串。 n 不大于 50,且至少存在一个字符不是任何字符串的首字母。
    输出描述:输出一个数,表示最大和是多少。
    输入例子:
    2
    ABC
    BCA
    输出例子:
    1875

一开始看漏了首位不能映射到0的条件…直接贪了..结果发现不太对…

哦贪心的方法就是算每个字母的权值和…用pair 搞一下…

处理的办法是如果10个字母都出现,那么先把没有在首位出现过的字母中权重最小的那个映射到0,再搞剩下的…

一个trick是…map映射到0..和某个key没有被映射过..产生了二义性….

窝的做法就是整体+1,最后再减回来..

然后因为某处手残卡了1个小时…???.

哎我果然是个废k了…..傻逼贪心都写不对QAQ

/* ***********************************************
Author :111qqz
Created Time :2017年03月29日 星期三 16时28分18秒
File Name :toutiao1.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=55;
int n;
string st[N];
pair <long long ,int > cnt[20];
LL ten[25];
map<char,int>mp;
set<char>Nhead;
bool head[25];
set<char>all;
set<char>used;
set< pair <long long ,char> > se;
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    cin>>n;
    ten[0] = 1;
    for ( int i = 1 ; i <= 15 ; i++) ten[i] = ten[i-1]*10LL;
    for ( int i = 1 ; i <= n ; i++) cin>>st[i];
    ms(cnt,0);
    ms(head,false);
    mp.clear();	//处理首位不能为0的思路:把不在头部出现的字母中,权值最小的映射到0//
            //只有当10个字母都出现了...否则就正常搞...
    for ( int i = 1 ; i <= n ; i++)
    {
        int len = st[i].length();
        for ( int j = 0 ; j < len ; j++)
        {
        int val = st[i][j]-'A';
        if (j==0) head[val] = true;
        all.insert(st[i][j]);
        LL ret = 1LL*ten[len-j-1];
        cnt[val].fst+=ret;
        cnt[val].sec = val;
        }
    }
    for ( int i = 0 ; i < 10 ; i++) if (!head[i]) Nhead.insert(i+'A');
//	for ( auto it = Nhead.begin() ; it!=Nhead.end() ; it++) printf("%c %lld\n",*it,cnt[*it-'A'].fst);
    if (all.size()==10)
    {
        LL mn = 1E18;
        int pid = -1;
        set<char>::iterator mn_it;
        for ( auto it = Nhead.begin();it!=Nhead.end() ;it++)
        {
    //	cout<<"*it"<<*it<<endl;
        if (cnt[*it-'A'].fst < mn)
        {
            mn = cnt[*it-'A'].fst;
            mn_it = it;
        }
        }
     //   cout<<"bbbbb!   "<<*mn_it<<endl;
        mp[*mn_it] = 1;
        cnt[*mn_it-'A'].fst = -1;
        used.insert(*mn_it);
    }
    sort(cnt,cnt+10);
//	for ( int i = 0 ; i < 10 ; i++) printf("%lld %d  \n",cnt[i].fst,cnt[i].sec); 
//	puts("");今日头条
    int num = all.size();	
    for ( int i = 9 ; i >= 0 ; i--)
    {
        if (cnt[i].fst==-1) continue;
        if (!mp[cnt[i].sec+'A'])
        mp[cnt[i].sec+'A'] = i+1;
    }
//	for ( auto it = mp.begin() ; it!=mp.end() ; it++) cout<<it->fst<<" "<<it->sec-1<<endl;
    LL sum = 0LL;
    for ( int i = 1 ; i <= n ; i++)
    {
        int len = st[i].length();
        for ( int j = 0 ; j < len ; j++)
        {
        LL val = mp[st[i][j]]-1;
        LL tmp = 1LL*val*ten[len-j-1];
    //	cout<<"tmp:"<<tmp<<endl;
        sum += tmp;
        }
    }
    cout<<sum<<endl;
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付