题目类型 贪心题
题目意思
给出 n 个数和 m 个字符串 (1 <= n,m <= 100)
字符串可以重复(重复的字符串 视为 一种字符串)
现在问把 n 个数分配给 m 种字符串 得到的值的和 最小和最大分别是多少 (例如把 3 分配给 "abc" 那么所有"abc" 字符串的值均为3)
解题方法
统计字符串的种类和每种有多少个
把 n 个数排序后 把最小的 m 个数分别分配给 按数量从大到小排列的 m 种串 即可得到和的最小值(n个数中的最小分配给数量最多的字符串)
把 n 个数排序后 把最大的 m 个数分别分配给 按数量从大到小排列的 m 种串 即可得到和的最小值(n个数中的最大分配给数量最多的字符串)
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1e2+10;
int a[MAXN];
int b[MAXN];
int main() {
int n, m;
while(cin>>n>>m) {
for( int i=0; i<n; i++ ) cin>>a[i];
sort(a, a + n);
set<string>ss;
set<string>::iterator ps;
map<string, int>mm;
string str;
for( int i=0; i<m; i++ ) {
cin>>str;
mm[str]++;
ss.insert(str);
}
int tn = 0;
for( ps=ss.begin(); ps != ss.end(); ps++ ) {
b[tn++] = mm[*ps];
}
int n_max = 0, n_min = 0;
sort(b, b + tn);
for( int i=0; i<tn; i++ ) {
n_min += b[tn-i-1] * a[i];
n_max += b[i] * a[n-tn+i];
}
cout<<n_min<<" "<<n_max<<endl;
}
return 0;
}