首页 > 其他分享 >P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G:贪心

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G:贪心

时间:2024-11-06 18:58:44浏览次数:3  
标签:NOIP2004 Repair Fence 果子 int 体力 合并 多多 heap

[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

题目描述

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 $n-1$ 次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ,并且已知果子的种类 数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

例如有 $3$ 种果子,数目依次为 $1$ , $2$ , $9$ 。可以先将 $1$ 、 $2$ 堆合并,新堆数目为 $3$ ,耗费体力为 $3$ 。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 $12$ ,耗费体力为 $12$ 。所以多多总共耗费体力 $=3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

输入格式

共两行。
第一行是一个整数 $n(1\leq n\leq 10000)$ ,表示果子的种类数。

第二行包含 $n$ 个整数,用空格分隔,第 $i$ 个整数 $a_i(1\leq a_i\leq 20000)$ 是第 $i$ 种果子的数目。

输出格式

一个整数,也就是最小的体力耗费值。输入数据保证这个值小于 $2^{31}$ 。

样例 #1

样例输入 #1

3 
1 2 9

样例输出 #1

15

提示

对于 $30%$ 的数据,保证有 $n \le 1000$:

对于 $50%$ 的数据,保证有 $n \le 5000$;

对于全部的数据,保证有 $n \le 10000$。
·····································
题解:huffman 树

include

include

include

include

const int N = 10010;
int a[N];
int n;
int res;
using namespace std;
int main()
{
cin >> n;
priority_queue<int, vector, greater>heap;//小根堆。
for (int i = 1; i <= n; i++)
{
cin >> a[i];
heap.push(a[i]);
}
while (heap.size() - 1)//根节点前一层。
{
int a = heap.top();
heap.pop();
int b = heap.top();
heap.pop();
res += a + b;
heap.push(a + b);//将合并的放入队列进行下次合并。
}
cout << res;

return 0;

}

标签:NOIP2004,Repair,Fence,果子,int,体力,合并,多多,heap
From: https://www.cnblogs.com/lixinran1006/p/18530854

相关文章

  • P1088 [NOIP2004 普及组] 火星人
    [NOIP2004普及组]火星人题目描述人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言,但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的,首先,火星人把一个非常大的数字告诉人类科学家,科学家破解这个数字的含义后,再把一个很小......
  • P1085 [NOIP2004 普及组] 不高兴的津津 难点:如何按要求实现打印最生气的天数.py
    """anger=0day=0foriinrange(7):inclass,extra=input(map(int,input().split()))anger=inclass+extraday+=1"""#将anger数组的大小排序,输出anger最大的那一天,但我无法将anger和day连接起来排序#解决办法是用max_anger和angriest_day两个变量,在七天的......
  • DirectX Repair(DirectX修复工具)V4.3增强版
    DirectX修复工具(DirectXRepair)是一款系统级工具软件,简便易用。本程序的主要功能是检测当前系统的DirectX状态,如果发现异常则进行修复。程序主要针对0xc000007b问题设计,可以完美修复该问题。本程序中包含了最新版的DirectXredist(Jun2010),并且全部DX文件都有Microsoft的数字......
  • P1091 [NOIP2004 提高组] 合唱队形
    分析题目知道求一个最长上升子序列和一个最长下降子序列的长度均为同一个起点的最长的长度。于是求点击查看代码#include<iostream>#include<stack>#include<cmath>#include<algorithm>#include<set>#include<vector>#include<climits>#include<string.h>#incl......
  • 锐明Crocus系统 RepairRecord.do SQL注入漏洞
    0x01产品描述:       明锐技术是一家专注于AI和视频技术的商用车智能物联(AIoT)解决方案提供商,Crocus系统是其核心产品之一。该系统旨在利用人工智能、高清视频、大数据和自动驾驶技术,提高企业或车队的运营效率,帮助商用车减少交通事故和货物丢失。通过车载摄像头、毫米波......
  • 【堆】【优先队列】[NOIP2004]合并果子
    https://ac.nowcoder.com/acm/contest/22669/I堆的用法Type:队列中存储元素的类型。例如int,double,pair<int,int>等。Container:底层存储数据的容器类型,默认为vector,但可以换成deque或其他容器。Compare:比较函数,用于决定优先级顺序。默认是less,表示最大堆。如果使用......
  • Using DISM to Check and Repair Windows Image
    Youcanusethe SFC (SystemFileChecker)and DISM (DeploymentImageServicingandManagement)commandstocheckandrepairtheintegrityofsystemfilesandComponentStoreofyourWindows(WindowsServer)image.Thesetoolscanbeextremelyusefulifyo......
  • P9891 [ICPC2018 Qingdao R] Repair the Artwork 题解
    所求即为选择的区间恰好包含所有\(a_i=2\)的位置的方案数。设所有\(a_i=2\)的位置\(i\)组成集合\(S\),考虑容斥被选中的位置是\(S\)的子集的方案数\(g(S)\)。设\(T\)为\(S\)的子集,\(T\)的贡献\(f(T)\)为:选中的位置都在\(T\)的子集中的方案数乘容斥系数\(......
  • P1091 [NOIP2004 提高组] 合唱队形
    [NOIP2004提高组]合唱队形题目描述$n$位同学站成一排,音乐老师要请其中的$n-k$位同学出列,使得剩下的$k$位同学排成合唱队形。合唱队形是指这样的一种队形:设$k$位同学从左到右依次编号为$1,2,$…$,k$,他们的身高分别为$t_1,t_2,$…$,t_k$,则他们的身高满足$t_1<\c......
  • A Walkthrough Using Acquire and Release Fences
    We’lltaketheexamplefrommypreviouspostandmodifyittouseC++11’sstandaloneacquireandreleasefences.Here’stheSendTestMessagefunction.Theatomicwriteisnowrelaxed,andareleasefencehasbeenplacedimmediatelybeforeit.voidSen......