★问题描述:
字母表 A 由 m 个英文字母组成。字母表中的每个英文字母都有一个权。一个单词的权是单词中每个字母的权之和。定义在字母表上的语言是由字母表中字母组成的不同单词的集
合。一个语言的权是语言中所有单词的权之和。 最小权语言问题要求对于给定的字母表,找到一个由 n 个单词组成的最小权语言。
★实验任务:
对于给定的字母表,找到一个由 n 个单词组成的最小权语言。
★数据输入
第一行有 2 个正整数 n 和 m,分别表示字母表 A 由 m(m<=26)个英文字母组成;语言由n(n<=10000)个单词组成。第 2 行有 m 个正整数表示字母表中的每个英文字母的权。
★数据输出
计算出的最小权语言的权值。
输入示例
3 2
2 5
输出示例
11
有人不知道答案是怎么来的,答案是 2 (2+2) 5 这样的
赤裸裸的优先队列水题。
根据贪心算法,每一次把最小的单词取出来,那么最后的权值最小。
那么对于取出的每个单词,要在加上字母表所有数,并且存入这个优先队列里面。
12月2号更新代码。
作业评优需要人品,同一个代码交上去时间会不一样。。
#include<cstdio> const int MAXN=300000; int data[30]; struct heap { int tree[MAXN]; int cur_size; heap(){cur_size=1;} void matain(int hole) { int child; int temp=tree[ hole ]; for(;( hole <<1 ) <=cur_size ; hole=child) { child= (hole << 1); if(child != cur_size && tree[child + 1 ] < tree [child] ) child++; if(tree[child] <temp) tree[hole]=tree[child]; else break; } tree[hole]=temp; } void build() { int i; for(i=(cur_size>>1 ) ; i>=0;i--) matain( i ); } int top() { return tree[ 1 ]; } void pop() { tree[1]=tree[cur_size--]; matain(1); } void push(int x) { int hole=++cur_size; for(; hole >1 && x < tree [(hole >>1)];hole>>=1) { tree[hole] = tree [ hole >> 1]; } tree[hole]=x; } }q; int main() { int n,m,i,j; scanf("%d%d",&n,&m); for( i=1;i<=m;i++) { scanf("%d",&q.tree[i]); q.cur_size=m; data[i]=q.tree[i]; } q.build(); int ans=0; for(i=0;i<n;i++) { int temp=q.top(); ans+=temp; q.pop(); int temp2; for(j=1;j<=m;j++) { temp2=temp+data[j]; q.push(temp2); } } printf("%d\n",ans); return 0; }