今日头条笔试题-最大映射(贪心)
有 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
1/* ***********************************************
2Author :111qqz
3Created Time :2017年03月29日 星期三 16时28分18秒
4File Name :toutiao1.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=55;
32int n;
33string st[N];
34pair <long long ,int > cnt[20];
35LL ten[25];
36map<char,int>mp;
37set<char>Nhead;
38bool head[25];
39set<char>all;
40set<char>used;
41set< pair <long long ,char> > se;
42int main()
43{
44 #ifndef ONLINE_JUDGE
45 freopen("code/in.txt","r",stdin);
46 #endif
47 cin>>n;
48 ten[0] = 1;
49 for ( int i = 1 ; i <= 15 ; i++) ten[i] = ten[i-1]*10LL;
50 for ( int i = 1 ; i <= n ; i++) cin>>st[i];
51 ms(cnt,0);
52 ms(head,false);
53 mp.clear(); //处理首位不能为0的思路:把不在头部出现的字母中,权值最小的映射到0//
54 //只有当10个字母都出现了...否则就正常搞...
55 for ( int i = 1 ; i <= n ; i++)
56 {
57 int len = st[i].length();
58 for ( int j = 0 ; j < len ; j++)
59 {
60 int val = st[i][j]-'A';
61 if (j==0) head[val] = true;
62 all.insert(st[i][j]);
63 LL ret = 1LL*ten[len-j-1];
64 cnt[val].fst+=ret;
65 cnt[val].sec = val;
66 }
67 }
68 for ( int i = 0 ; i < 10 ; i++) if (!head[i]) Nhead.insert(i+'A');
69// for ( auto it = Nhead.begin() ; it!=Nhead.end() ; it++) printf("%c %lld\n",*it,cnt[*it-'A'].fst);
70 if (all.size()==10)
71 {
72 LL mn = 1E18;
73 int pid = -1;
74 set<char>::iterator mn_it;
75 for ( auto it = Nhead.begin();it!=Nhead.end() ;it++)
76 {
77 // cout<<"*it"<<*it<<endl;
78 if (cnt[*it-'A'].fst < mn)
79 {
80 mn = cnt[*it-'A'].fst;
81 mn_it = it;
82 }
83 }
84 // cout<<"bbbbb! "<<*mn_it<<endl;
85 mp[*mn_it] = 1;
86 cnt[*mn_it-'A'].fst = -1;
87 used.insert(*mn_it);
88 }
89 sort(cnt,cnt+10);
90// for ( int i = 0 ; i < 10 ; i++) printf("%lld %d \n",cnt[i].fst,cnt[i].sec);
91// puts("");今日头条
92 int num = all.size();
93 for ( int i = 9 ; i >= 0 ; i--)
94 {
95 if (cnt[i].fst==-1) continue;
96 if (!mp[cnt[i].sec+'A'])
97 mp[cnt[i].sec+'A'] = i+1;
98 }
99// for ( auto it = mp.begin() ; it!=mp.end() ; it++) cout<<it->fst<<" "<<it->sec-1<<endl;
100 LL sum = 0LL;
101 for ( int i = 1 ; i <= n ; i++)
102 {
103 int len = st[i].length();
104 for ( int j = 0 ; j < len ; j++)
105 {
106 LL val = mp[st[i][j]]-1;
107 LL tmp = 1LL*val*ten[len-j-1];
108 // cout<<"tmp:"<<tmp<<endl;
109 sum += tmp;
110 }
111 }
112 cout<<sum<<endl;
113 #ifndef ONLINE_JUDGE
114 fclose(stdin);
115 #endif
116 return 0;
117}