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

技术P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fe

p 1090【noip 2004改良组】联合果/【usaco 06 nov】栅栏修复G

题目描述

在一个果园里,多多把所有的水果都击倒了,并根据不同的水果种类把它们分成不同的堆。多多决定把所有的水果组合成一堆。

每次合并,多多可以将两堆水果合并在一起,消耗的体力等于两堆水果的重量之和。可以看出所有的水果都经过n-1n?一次合并后,只剩下一堆了。合并果实消耗的总体力等于每次合并消耗的体力之和。

因为要花大力气把这些水果搬回家,所以在合并水果的时候要尽量节约能源。假设每个水果的重量为11,水果的种类数和每种水果的数量都是已知的,那么你的任务就是设计一个组合序列方案,使更多的水果消耗的体力最小,并输出这个最小体力消耗值。

比如水果有33种,依次是11种、22种、99种。首先,11堆和22堆可以合并。新桩数33根,能耗33。然后将新桩与原第三桩合并,得到新桩,编号为1212,体力为1212。所以需要很大的体力=3 12=15=3 12=15。可以证明1515是最小物理消耗值。

输入格式

总共两排。

第一行是整数n(1n10000),表示水果的种类数。

第二行包含由空格分隔的n个整数,第I个整数ai?(1ai?20000)是第I个水果的数量。

输出格式

整数,即最小体力消耗值。输入数据以确保该值小于2 {31}。

输入输出样例

输入#1副本。

1 2 9

输出#1副本

15

说明/提示

对于30%的数据,确保n1000:

对于50%的数据,确保n5000;

对于所有数据,确保n10000。

分析

从观察可以看出,合并得越早,计算的次数越多,所以贪心策略是先合并小堆。

#includebits/stdc。h

使用命名空间标准;

int n;

priority_queueint,vectorint,greater int a;

int ans

int main()

{

cinn

for(int I=1;I=n;(一)

{

int p;

cinp

a . push(p);

}

而(a . size)(1)

{

int j=a . top();

a . pop();

int k=a . top();

a . pop();

ans=(j k);

a . push(j . k);

}

coutansendl

返回0;

}

内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/100410.html

(0)

相关推荐

  • 毫不犹豫英语,英语单词confront的用法

    技术毫不犹豫英语,英语单词confront的用法confront用于动词毫不犹豫英语。confront是及物动词。confront过去时:confronted,confront第三人称:confronts。动词随着人称、

    生活 2021年10月21日
  • 抖音20元1000粉丝网站,刷抖音粉丝的好处有哪些?

    技术抖音20元1000粉丝网站,刷抖音粉丝的好处有哪些?根据小编的了解,现在可以说在全民各行各业各个年龄层都大火的抖音短视频吸粉的速度也是十分快速的,而上面有很多网红粉丝量已经让人眼前一亮,大大惊艳了吃瓜群众。甚至有的普

    测评 2021年10月21日
  • 怎么使用flutter中Checkbox复选框的全选与删除

    技术怎么使用flutter中Checkbox复选框的全选与删除本篇内容介绍了“怎么使用flutter中Checkbox复选框的全选与删除”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大

    攻略 2021年10月29日
  • php如何实现身份证号替换为星号

    技术php如何实现身份证号替换为星号本篇内容主要讲解“php如何实现身份证号替换为星号”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“php如何实现身份证号替换为星号”吧!

    攻略 2021年11月17日
  • 如何使用Black自由格式化Python

    技术如何使用Black自由格式化Python如何使用Black自由格式化Python,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。在我们覆盖

    攻略 2021年10月26日
  • new的反义词,“new”的反义词是什么

    技术new的反义词,“new”的反义词是什么new的反义词是oldnew的反义词;old;英 [əʊld] 美 [oʊld] adj.老的;古老的;以前的;(用于指称被替代的东西)原来的n.古时比较级: older

    生活 2021年10月27日