中南林业科技大学第十一届程序设计大赛组合游戏牛客网哈希算法-白红宇

中南林业科技大学第十一届程序设计大赛组合游戏牛客网哈希算法

阅读量：6487 次

发布时间：2019-06-23

本文共 1285 字，大约阅读时间需要 4 分钟。

链接：

来源：牛客网

题目描述

2018年4月8日星期日，小龙沉迷于一个叫做组合的游戏。

游戏规则是这样的，原本有一个长度为A的大木板，现在把它分成了n份长度可能不一样的木板。每一个模板的长度为X_i，每次游戏都要把这些木板组合为一个完整的木板，但是小龙每次只能拿两个小木板去组合成为一个，然后把这新木板和剩下的木板放在一起，重复以上步骤直到最后只剩下一个木板。

每次组合木板会花费K个金币，K等于拿起的两个木板长度之和，问小明每次玩游戏最少花费是多少？

例如：当有n=3块木板的时候

每一块木板的长度分别是是 1、2、3

第一次拿长度为1 和 2 的木板拼接成长度为3的木板，花费3个金币

此时有两块木板，长度分别为3 和 3

第二次拿长度为3 和3 的木板拼接成长度为6的木板，花费6个金币

总共花费9个金币（最少）。

输入描述:

输入有多组，每一组第一行是n(1 < n <= 200)

接下来第二行到第n+1行，第i+1行表示小木板的长度X

(X

<= 200)

输出描述:

输出每个样例的最少花费，每个答案占据一行。

示例1

输入

输出

9 一个典型的哈希算法题目，开始写的时候硬是没有想起来（基础还是不牢固。。。）

#include#include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define debug(a) cout << #a << ": " << a << endl;using namespace std ;const int maxn = 1e4 + 20 ;typedef unsigned long long ll;int main() { ios::sync_with_stdio(false); ll n, a; while( cin >> n ) { priority_queue< int, vector
                   
                    , greater
                    
                      > q; for( int i = 0; i < n; i ++ ) { cin >> a; q.push(a); } ll sum = 0; while( q.size() > 1 ) { ll ta = q.top(); q.pop(); ll tb = q.top(); q.pop(); sum = sum + ta + tb; q.push( ta + tb ); } cout << sum << endl; } return 0 ;}

转载于:https://www.cnblogs.com/l609929321/p/9144324.html

你可能感兴趣的文章

系统诊断小技巧（7）：利用Iptables进行排查和诊断的简易方案