#UVa:10954-Add All

灆洢 2015-07-26 00:37:12

可以利用Heap或是Priority Queue來解這題。先將最小的兩個數字加起來再丟回數列中,以此類推,直到只剩下一個數字為止。在做加起來的同時,也把此數值加進cost,這樣cost即是解答。

P.S. 類似Huffman演算法。

C++(0.018)

/*******************************************************/
/* UVa 10954 Add All                                   */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2015/07/26                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main(){
  int N;
  while( scanf("%d", &N) != EOF && N != 0 ){
    priority_queue<int, vector<int>, greater<int> > nums;
    int num;
    for( int i = 0 ; i < N ; ++i ){
      scanf("%d", &num);
      nums.push(num);
    }

    int cost = 0;
    while( nums.size() > 1 ){
      int a = nums.top(); nums.pop();
      int b = nums.top(); nums.pop();
      nums.push(a+b);
      cost += a+b;
    }

    printf("%d\n", cost);
  }

  return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料