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

有 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;
}