# APCS實作題2017年10月第4題：物品堆疊 (Stacking)

> 第1版：2023年2月26日
> 第2版：2023年6月14日，加上 C++ 語法
> 第3版：2024年12月1日，在讀了吳邦一教授的 AP325 講義之後重寫
> 作者：王一哲
> 題目來源：[106年10月28日實作題第4題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1061028APCSImplementation.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c471)

<br />

## 題目

### 問題描述

某個自動化系統中有一個存取物品的子系統，該系統是將 N 個物品堆在一個垂直的貨架上，每個物品各佔一層。系統運作的方式如下：每次只會取用一個物品，取用時必須先將在其上方的物品貨架升高，取用後必須將該物品放回，然後將剛才升起的貨架降回原始位置，之後才會進行下一個物品的取用。

每一次升高某些物品所需要消耗的能量是以這些物品的總重來計算，在此我們忽略貨架的重量以及其他可能的消耗。現在有 N 個物品，第 i 個物品的重量是 w(i) 需要取用的次數為 f(i)，我們需要決定如何擺放這些物品的順序來讓消耗的能量越小越好。舉例來說，有兩個物品 w(1)=1、w(2)=2、f(1)=3、f(2)=4，也就是說物品 1 的重量是 1 需取用 3 次，物品 2 的重量是 2 需取用 4 次。我們有兩個可能的擺放順序(由上而下)：
- (1,2)，也就是物品 1 放在上方，2 在下方。那麼，取用 1 的時候不需要能量，而每次取用 2 的能量消耗是 w(1)=1，因為 2 需取用 f(2)=4 次，所以消耗能量數為 w(1)\*f(2)=4。
- (2,1)，也就是物品 2 放在 1 的上方。那麼，取用 2 的時候不需要能量，而每次取用 1 的能量消耗是 w(2)=2 ，因為 1 需取用 f(1)=3 次，所以消耗能量數=w(2)\*f(1)=6 。

在所有可能的兩種擺放順序中，最少的能量是 4，所以答案是 4。再舉一例，若有三物品而 w(1)=3、w(2)=4、w(3)=5、f(1)=1、f(2)=2、f(3)=3。假設由上而下以(3,2,1)的順序，此時能量計算方式如下：取用物品 3 不需要能量，取用物品 2 消耗 w(3)\*f(2)=10，取用物品 1 消耗(w(3)+w(2))\*f(1)=9，總計能量為 19。如果以(1,2,3)的順序，則消耗能量為3\*2+(3+4)\*3=27。事實上，我們一共有 3!=6 種可能的擺放順序，其中順序(3,2,1)可以得到最小消耗能量 19。

<br />

### 輸入格式

輸入的第一行是物品件數 N，第二行有 N 個正整數，依序是各物品的重量 w(1)、w(2)、…、w(N)，重量皆不超過 1000 且以一個空白間隔。第三行有 N 個正整數，依序是各物品的取用次數 f(1)、f(2)、…、f(N)，次數皆為 1000 以內的正整數，以一個空白間隔。
<br />

### 輸出格式

輸出最小能量消耗值，以換行結尾。所求答案不會超過 63 個位元所能表示的正整數。
<br />

### 範例一(第 1、3 子題)：輸入

2
20 10
1 1

### 範例一：正確輸出

10

<br />

### 範例二(第 2、4 子題)：輸入

3
3 4 5
1 2 3

### 範例二：正確輸出

19

<br />

### 評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 1 秒，依正確通過測資筆數給分。其中：
- 第 1 子題組 10 分，N = 2，且取用次數 f(1)=f(2)=1。
- 第 2 子題組 20 分，N = 3。
- 第 3 子題組 45 分，N ≤ 1,000，且每一個物品 i 的取用次數 f(i)=1。
- 第 4 子題組 25 分，N ≤ 100,000。

<br />

## Python 程式碼

花費時間最久為 0.3 s，使用記憶體最多為 32.7 MB，通過測試。

N = int(input())  # 物品數量
ws = list(map(int, input().split()))  # 重量
fs = list(map(int, input().split()))  # 取用次數
wf = sorted([(w, f) for w, f in zip(ws, fs)],
        key = lambda x: x[0] / x[1] if x[1] != 0 else 1001)  # 又輕又常被取用的物品放上面
wsum, ans = wf[0][0], 0  # wsum 總重量，先放入首項；ans 預設為 0
for w, f in wf[1:]:  # 依序讀取 wf[1] ~ wf[-1]
    ans += wsum*f  # ans 加上目前的總重量乘以取用次數
    wsum += w  # 更新總重量
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

花費時間最久為 39 ms，使用記憶體最多為 1.9 MB，通過測試。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    LL N; cin >> N;  // 物品數量
    vector<pair<LL, LL>> wf (N);  // 重量 w，取用次數 f
    for(LL i=0; i<N; i++) cin >> wf[i].first;
    for(LL i=0; i<N; i++) cin >> wf[i].second;
    sort(wf.begin(), wf.end(), [](pair<LL, LL> a, pair<LL, LL> b) {
         return a.first * b.second < b.first * a.second; } );  // 又輕又常被取用的物品放上面
    LL wsum = wf[0].first, ans = 0;  // wsum 總重量，先放入首項；ans 預設為 0
    for(LL i=1, w, f; i<N; i++) {  // 依序讀取 wf[1] ~ wf[-1]
        w = wf[i].first; f = wf[i].second;
        ans += wsum*f;  // ans 加上目前的總重量乘以取用次數
        wsum += w;  // 更新總重量
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br />

---

###### tags:`APCS`、`C++`、`Python`