1736. 扑克游戏 (Standard IO)

Time Limits: 1000 ms Memory Limits: 128000 KB

Description

  有一棵无穷大的满二叉树,根为star,其余所有点的权值为点到根的距离,如图:

  JZOJ 1736. 扑克游戏 (Standard IO)-LMLPHP

  现在你有一些扑克牌,点数从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

【样例说明】

  JZOJ 1736. 扑克游戏 (Standard IO)-LMLPHP

【数据范围】

  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:

看过我其他博文的有没有感觉代码很熟悉

没错,就是合并果子

05-19 07:03