# APCS實作題2017年10月第4題：物品堆疊 (Stacking)
> 第1版：2023年2月26日
> 第2版：2023年6月14日，加上 C++ 語法
> 作者：王一哲
> 題目來源：[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 程式碼
### 方法1：使用自訂類別
```python=
import functools
# 自訂類別 Box，包含箱子的重量 w、取用次數 f
class Box:
def __init__(self, w, f):
self.w = w
self.f = f
# 自訂比較用的函式，比較箱子 a、b
def mycmp(a, b):
if a.w*b.f > b.w*a.f: return 1 # a 放下面、索引值大
else: return -1 # a 放上面、索引值小
# 讀取箱子個數 N、重量 ws、取用次數 fs
N = int(input())
ws = list(map(int, input().split()))
fs = list(map(int, input().split()))
# 用 Box 建立串列 boxes，再用 mycmp 作為 key 排序資料
boxes = [Box(ws[i], fs[i]) for i in range(N)]
boxes.sort(key=functools.cmp_to_key(mycmp))
# 計算第i個箱子上方箱子總重量 weight、取用第i個箱子消耗的能量 energy
weight, energy = 0, 0
for i in range(N-1):
weight += boxes[i].w
energy += weight*boxes[i+1].f
print(energy) # 印出題目要的答案
```
<br />
1. 第4 ~ 7行：自訂類別 Box，包含箱子的重量 w、取用次數 f。
2. 第10 ~ 12行：自訂函式 mycmp，用來作為排序資料時的 key 值。若輸入 Box 物件 a、b，若 **a.w\*b.f > b.w\*a.f**，使用 sort 排序資料時，將 a 放下面、索引值大；反之，a 放上面、索引值小。
3. 第15 ~ 17行：從標準輸入讀取箱子個數 N、重量 ws、取用次數 fs。
4. 第20、21行：用 Box 建立串列 boxes，再用 functools.cmp_to_key(mycmp) 作為 key 排序資料，需要先引入函式庫 functools。
5. 第24 ~ 27行：計算第i個箱子上方箱子總重量 weight、取用第i個箱子消耗的能量 energy。
6. 第29行：提交程式碼測試時維一印出的值。
7. ZeroJudge 測試結果，第18筆測資花費時間最久為 2.2 s，使用記憶體 43.8 MB，通過測試。
<br /><br />
### 方法2：使用 zip 合併資料
```python=
import functools
# 自訂比較用的函式，比較箱子 a、b
def mycmp(a, b):
if a[0]*b[1] > b[0]*a[1]: return 1 # a 放下面、索引值大
else: return -1 # a 放上面、索引值小
# 讀取箱子個數 N、重量 ws、取用次數 fs
N = int(input())
ws = list(map(int, input().split()))
fs = list(map(int, input().split()))
data = list(zip(ws, fs))
# 用 mycmp 作為 key 排序資料
data.sort(key=functools.cmp_to_key(mycmp))
# 計算第i個箱子上方箱子總重量 weight、取用第i個箱子消耗的能量 energy
weight, energy = 0, 0
for i in range(N-1):
weight += data[i][0]
energy += weight*data[i+1][1]
print(energy) # 印出題目要的答案
```
<br />
這個作法是從[參考資料2](https://cbjsprogramdiary.com/2022/12/28/c471-apcs-%e7%89%a9%e5%93%81%e5%a0%86%e7%96%8a-stacking/)抄來的，用 zip 將 ws、fs 合併成二維串列 data，每個元素的內容為箱子的 (重量, 取用次數)，由於不需要再多跑一次 for 迴圈並用自訂類別 Box 産生物件，運作時間會比方法1還短。ZeroJudge 測試結果，第15及19筆測資花費時間最久為 1.6 s，使用記憶體 33.2 MB，通過測試。
<br /><br />
## C++ 程式碼
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;
// 自訂結構體 Box，包含箱子的重量 w、取用次數 f
typedef struct _Box {
int w, f;
} Box;
// 自訂比較用的函式，比較箱子 a、b，
bool mycmp(Box a, Box b) {
return a.w*b.f < b.w*a.f;
}
int main(int argc, char* argv[]) {
// 由標準輸入讀取箱子個數 N
int N; cin >> N;
// 用 Box 建立陣列 boxes，再用 mycmp 作為排序資料時的比較方式
Box boxes[N];
for(int i=0; i<N; i++) cin >> boxes[i].w;
for(int i=0; i<N; i++) cin >> boxes[i].f;
sort(boxes, boxes+N, mycmp);
// 除錯用，印出排序後的資料
//for(int i=0; i<N; i++) cout << boxes[i].w << " ";
//cout << endl;
// 計算第i個箱子上方箱子總重量 weight、取用第i個箱子消耗的能量 energy
long long weight = 0, energy = 0;
for(int i=0; i<N-1; i++) {
weight += boxes[i].w;
energy += weight*boxes[i+1].f;
}
// 印出題目要的答案
cout << energy << endl;
return 0;
}
```
<br />
1. 程式運作邏輯與 Python 程式碼方法1相同。
2. 第6 ~ 8行：自訂結構體 Box，包含箱子的重量 w、取用次數 f。
3. 第11 ~ 13行：自訂函式 mycmp，用來作為排序資料時的比較方式，若 **a.w\*b.f < b.w\*a.f**，a 放上面、索引值小。 ```
4. 第17行：由標準輸入讀取箱子個數 N。
5. 第19 ~ 22行：用 Box 建立陣列 boxes，再用 mycmp 作為排序資料時的比較方式。
6. 第28 ~ 32行：計算第i個箱子上方箱子總重量 weight、取用第i個箱子消耗的能量 energy，需要使用 long long 作為 weight、energy 的格式。
7. 第35行：提交程式碼測試時維一印出的值。
8. ZeroJudge 測試結果，第18筆測資花費時間最久為 0.2 s，使用記憶體 1.1 MB，通過測試。
<br /><br />
## 參考資料
1. 黃建庭（2019）。**C++程式設計解題入門 融入程式設計競賽與APCS實作題（第二版）**。臺北市：碁峰資訊。 4-29
2. https://cbjsprogramdiary.com/2022/12/28/c471-apcs-%e7%89%a9%e5%93%81%e5%a0%86%e7%96%8a-stacking/
3. https://www.geeksforgeeks.org/how-does-the-functools-cmp_to_key-function-works-in-python/
<br />
---
###### tags:`APCS`、`C++`、`Python`
Sign in with Wallet
Connect another wallet