1736. 扑克游戏 (Standard IO)
Time Limits: 1000 ms Memory Limits: 128000 KB
Description
有一棵无穷大的满二叉树,根为star,其余所有点的权值为点到根的距离,如图:
现在你有一些扑克牌,点数从1到13,你要把这些扑克牌全部放到这个树上:
1. 当你把点数为i的扑克牌放在权值为j的点上,那么你会得到i*j的分数。
2. 当你把一个扑克牌放在一个节点上,那么你就不能把别的扑克牌放在这个节点以及这个节点的子树上。
你的目标是最小化你的得分。
Input
文件名为 poker.in
输入第一行为一个数字N,表示你有的扑克牌数;
接下来一行N个数字,数字在1到13之间。
Output
文件名为 poker.out
一个数字,最小得分。
Sample Input
3
5 10 13
Sample Output
43
Data Constraint
Hint
【样例说明】
【数据范围】
30%数据 N<=100
100%数据满足1<=N<=10000.
题解
这是今天做的第四道哈夫曼树专题了
总结一下
解法大同小异,只是换个方式问而已
类似这道题,题目说得分是 i * j 其实就是哈夫曼树,模型转换一下就好了
代码
#include<iostream>
#include<iostream>
#include<cstdio>
#define INF 2147483647
#define N 20000
using namespace std;
long long dui[N*2+1],top;
void add(long x)
{ long now;
dui[++top]=x;
for(now=top;dui[now/2]>dui[now]&&now>1;now/=2)
swap(dui[now],dui[now/2]);
}
long qu()
{ long ans=dui[1],now;
bool t=false;
dui[1]=INF;
now=1;
while(!t){
t=true;
if(now*2==top||dui[now*2]<dui[now*2+1]){
if(dui[now]>dui[now*2]){
swap(dui[now],dui[now*2]);
now=now*2;
t=false;
}
}else if(now*2+1<=top)
if(dui[now]>dui[now*2+1]){
swap(dui[now],dui[now*2+1]);
now=now*2+1;
t=false;
}
}
return ans;
}
int main()
{ long n,m,i,q;
long long ans=0;
scanf("%ld",&n);
for(i=1;i<=n;i++){
scanf("%ld",&q);
add(q);
}
for(i=1;i<n;i++){
q=qu()+qu();
ans+=q;
add(q);
}
printf("%lld\n",ans);
return 0;
}
ps:
看过我其他博文的有没有感觉代码很熟悉
没错,就是合并果子