扑克游戏

(poker)

题目描述:

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

现在你有一些扑克牌，点数从1到13，你要把这些扑克牌全部放到这个树上：

1. 当你把点数为i的扑克牌放在权值为j的点上，那么你会得到i*j的分数。
2. 当你把一个扑克牌放在一个节点上，那么你就不能把别的扑克牌放在这个节点以及这个节点的子树上。

你的目标是最小化你的得分。

输入:

    文件名为 poker.in

         输入第一行为一个数字N，表示你有的扑克牌数；

接下来一行N个数字，数字在1到13之间。

输出:

文件名为 poker.out

         一个数字，最小得分。

样例输入:

3

5 10 13

样例输出:

43

 

样例说明：

 

数据范围:

          30%数据 N<=100

100%数据满足1<=N<=10000.

 

 

就这破（水）题暴了我好久时间，其实是一道水题。想到这棵树的每个节点只可能有0个或者2个儿子（这很显然）。这不就是huffman的的特点吗！然而吾并没有往这上面想，其实这道题就是合并果子！想象题目中输入数据的第二行给出的就是N个字符的出现频率，这特么就是huffman！唉，破烂题目毁我一生！

 

#include 
     
      #include 
      
       const int maxn = 10005;int n, a[maxn], b[maxn], head1, head2, tail2, ans, t, flag;int main(void) {    freopen("poker.in", "r", stdin);    freopen("poker.out", "w", stdout);    scanf("%d", &n);    for (int i = 0; i < n; ++i) {        scanf("%d", a + i);    }    std::sort(a, a + n);        for (int i = 1; i < n; ++i) {        t = 2147483647;        flag = -1;        if (head1 + 1 < n && t > a[head1] + a[head1 + 1]) {            t = a[head1] + a[head1 + 1];            flag = 0;        }        if (head1 < n && head2 < tail2 && t > a[head1] + b[head2]) {            t = a[head1] + b[head2];            flag = 1;        }        if (head2 + 1 < tail2 && t > b[head2] + b[head2 + 1]) {            t = b[head2] + b[head2 + 1];            flag = 2;        }        if (!flag) {            head1 += 2;        }        else if (flag == 1) {            ++head1;            ++head2;        }        else {            head2 += 2;        }        b[tail2++] = t;        ans += t;    }    printf("%d\n", ans);    return 0;}