wjw的树切割问题

Problem A: wjw的树

Description

wjw在很早以前种了一棵树，这棵树过了这么多年，已经长到了n米高，wjw为了建造火车站，决定把这棵树给砍倒当作木材，但是这课树太高了，于是wjw准备把这棵树切成m份，每份长度分别为a1,a2,a3...am,显然这种技术活需要一个专业人员——木匠,但是木匠是收费的，他每次切一根长度为x的木材就要收x元，现在wjw想知道最少需要花多少钱就能把这棵树切成他想要的木材。

Input

有多组输入数据，对于每组数据，输入第一行是两个正整数n, m(1≤m≤n≤1000)，第二行包含m个正整数，分别是a1,a2,a3...am。输入保证这m个数之和为n。

Output

对于每组数据，输出最少的花费

Sample Input

8 3

2 2 4

6 2

3 3

11 3

5 1 5

Sample Output

Case #1: 12

Case #2: 6

Case #3: 17

【分析】

倒过来想...不是把长度为n的木材分割，而是把m块木材合并成长度为n的木材，那么显然可以发现贪心的方法就是每次合并最小的两个木材...所以..插入排序or优先队列..直接做就好了

【代码】

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <queue>

using namespace std;

priority_queue<int,vector<int>,greater<int> >a;

int main()

{

int pp=1;

int n,m,x,y;

while(scanf("%d%d",&n,&m))

{

while(!a.empty())a.pop();

for(int i=0;i<m;i++)

{

scanf("%d",&x);

a.push(x);

}

int ans=0;

for(int i=0;i<m-1;i++)

{

x=a.top();a.pop();

y=a.top();a.pop();

ans+=x+y;

a.push(x+y);

}

printf("Case #%d: %dn",pp++,ans);

}

return 0;

}