2020 蓝桥杯大学模拟赛(三) - 程序设计：养猫题解

素颜马尾好姑娘i 2022-12-28 14:15 153阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入格式
     *  输出格式
     *  数据范围
     *  样例输入
     *  样例输出
 *  算法分析
 *  解题代码

--------------------

# 题目描述 #

众所周知的，⼩明家⾥有好多猫，经过⼀次“猫⼝普查”，我们得到了以下信息：

⼩明家⾥有 `n` 只猫，第 `i` 只猫的体重是 **ai** 。然⽽⼩明热爱虐猫（并不），他决定对这些猫做⼀些有 ♂趣的事情

经过了两年半的练习之后，这些猫已经能完全听懂⼩明的指令了。

⼩明的指令分成两个阶段，具体步骤如下：

*  1.指定⼀种颜⾊，所有这种颜⾊的猫都会从猫窝⾥跑出来，此时⼩明需要付出总共为这些猫的体重的代价。例如，现在⼩明有三只红⾊的猫，体重分别为`1,2,3`，还有两只蓝⾊的猫，体重分别为 `7,8` 。此时如果⼩明声明的颜⾊是红⾊，那么所有红⾊的猫会出来，⼩明需要⽀付的代价为 `6` 。如果⼩明声明的颜⾊是蓝⾊，那么所有蓝⾊的猫会出来，⼩明需要⽀付的代价为 `15` 。
 *  2.对于现在出来的这些猫，⼩明选择其中的⼀部分，将他们染成⼀种新的颜⾊。然后放回所有的猫。

初始时所有猫都是⽩⾊。现在⼩明想知道，如果想要使得这些猫两两颜⾊都不同，最少需要花费多 少代价。

## 输入格式 ##

> 第一行一个整数 `n`,表示一共有 `n` 只猫,接下来一行 `n` 个数 **ai** 意义如题所示

## 输出格式 ##

> 输出⼀⾏⼀个整数表示最⼩代价

## 数据范围 ##

![1][]

## 样例输入 ##

4 
    6 7 70 25

## 样例输出 ##

159

# 算法分析 #

一开始的想法是将猫的代价从大到小排序，然后每次挑出最大代价的猫去染色，但是这个算法对于样例输入的代价`6,7,70,25`是可行的，但是如果除去最大代价的剩下的猫的代价，要比最大猫的代价更大，那这个算法就不能保证最小代价

例如：`69,70,71,72`

![2][]

可以观察发现，**这是一颗哈夫曼树，也就是说这道题应该从小问题考虑到总体，而不是从整体模拟选猫的过程**

# 解题代码 #

#include <iostream>
    #include <functional>
    #include <algorithm>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    //优先队列模拟哈夫曼树
    priority_queue<long long , vector<long long>, greater<long long>> head;
    int n;
    int a[100005];
    
    int main()
    {
        
        cin >> n;
        for(int i = 0; i < n; i++){
        
            cin >> a[i];
            head.push(a[i]);
        }
        
        long long sum = 0;
        for(int i = 0; i < n - 1; i++){
        
            long long a = head.top();
            head.pop();
            long long b = head.top();
            head.pop();
            
            long long c = a + b;
            sum += c;	//每个分支节点就是要加和的权重
            head.push(c);
        }
        
        cout << sum << endl;
        
        return 0;
    }

[1]: /images/20221120/a654e149d05e4fda9a3f358a6c543ca7.png
[2]: /images/20221120/da8ca671f62b482385ab440cfabd896f.png