国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

51Nod - 1117 優先隊列

2019-11-14 13:14:53
字體:
來源:轉載
供稿:網友

題意:

一位老木匠需要將一根長的木棒切成N段。每段的長度分別為L1,L2,......,LN(1 <= L1,L2,…,LN <= 1000,且均為整數)個長度單位。我們認為切割時僅在整數點處切且沒有木材損失。木匠發現,每一次切割花費的體力與該木棒的長度成正比,不妨設切割長度為1的木棒花費1單位體力。例如:若N=3,L1 = 3,L2 = 4,L3 = 5,則木棒原長為12,木匠可以有多種切法,如:先將12切成3+9.,花費12體力,再將9切成4+5,花費9體力,一共花費21體力;還可以先將12切成4+8,花費12體力,再將8切成3+5,花費8體力,一共花費20體力。顯然,后者比前者更省體力。那么,木匠至少要花費多少體力才能完成切割任務呢?Input
第1行:1個整數N(2 <= N <= 50000)第2 - N + 1行:每行1個整數Li(1 <= Li <= 1000)。Output
輸出最小的體力消耗。Input示例
3345Output示例
19

思路:

優先隊列水題。

代碼:

#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 10;int a[MAXN];int main() {    int n;    scanf("%d", &n);    PRiority_queue <int, vector <int>, greater <int> > que;    for (int i = 1; i <= n; i++) {        scanf("%d", &a[i]);        que.push(a[i]);    }    int ans = 0;    while (que.size() > 1) {        int x = que.top(); que.pop();        int y = que.top(); que.pop();        que.push(x + y);        ans += x + y;    }    printf("%d/n", ans);    return 0;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 洱源县| 凌源市| 康乐县| 永川市| 漾濞| 兴化市| 泾川县| 宽城| 托里县| 平谷区| 阿拉尔市| 融水| 双流县| 昌乐县| 历史| 池州市| 合江县| 秦皇岛市| 北碚区| 赤城县| 庄河市| 遂川县| 广水市| 阿坝县| 普宁市| 曲松县| 垦利县| 蒙城县| 尖扎县| 南漳县| 内丘县| 藁城市| 仁寿县| 荣昌县| 米林县| 城市| 荣昌县| 天门市| 肥西县| 酉阳| 富民县|