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

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：

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

没错，就是合并果子

巴特西

JZOJ 1736. 扑克游戏 (Standard IO)