f606-流量
題目解析
有 ( n ) 個伺服器編號從 0 到 ( n-1 ),以及 ( m ) 個城市編號從 0 到 ( m-1 )。每個伺服器需要傳送資料到各城市,已知每個伺服器 ( i ) 傳送到城市 ( j ) 的流量為 ( Q[i][j] )。
工程師正在規劃將伺服器搬遷到城市中,對於一個方案 ( c = (c_1, c_2, …, c_n) ),表示編號 ( i ) 的伺服器要放在城市 ( c_i )。
城市之間資料傳輸是需要費用的。若城市 ( u ) 要傳送資料到城市 ( v ),費用的計算法如下:
- 若 ( u = v ),單位流量需要 1 塊錢。
- 若 ( u != v ),小於等於 1000 的流量每單位 3 塊錢,大於 1000 的部分每單位 2 塊錢。
若某伺服器有多個城市需要傳送資料到城市 ( u ),會先將這些總量相加再計算費用。
工程師們總共提出了 ( k ) 種方案,請你找出花費最少的方案所需的費用。
解題方向
- 解析輸入資料,讀取伺服器數量 ( n )、城市數量 ( m )、方案數量 ( k ) 以及每個伺服器對每個城市的流量矩陣 ( Q )。
- 建立並初始化花費列表 ( cost )。
- 對每個方案計算伺服器配置的流量矩陣 ( flow )。
- 根據流量計算每個方案的總費用。
- 找出最小費用並輸出。
程式解析
- 輸入與初始化
- 這行程式碼從輸入中讀取三個整數n、m、k,分別表示伺服器的數量、城市的數量和方案的數量。
- 讀取流量矩陣Q
- 這段程式碼從輸入中讀取n行,每行包含m個整數,存儲在二維列表Q中。這表示每個伺服器到每個城市的流量。
- 初始化花費列表
- 這行程式碼初始化一個列表cost,用來存儲每個方案的總花費,初始值全部設為 0。
- 計算每個方案的花費
- 這段程式碼對每個方案進行以下步驟:
- 讀取一個方案c,表示每個伺服器的位置。
- 初始化一個新的流量矩陣flow,用來存儲每個城市到其他城市的總流量。
- 遍歷每個伺服器x到每個城市y的流量,將其加到flow 矩陣中對應的位置。
- 根據流量矩陣flow 計算每個城市間的傳輸費用並累加到總花費中:
- 若伺服器與城市相同,則每單位流量費用為 1。
- 若伺服器與城市不同,根據流量大小計算費用,小於等於 1000 的部分每單位 3 塊錢,大於 1000 的部分每單位 2 塊錢。
- 找出最小花費並輸出
- 這段程式碼找出所有方案中花費最小的方案,並輸出最小花費。
完整程式碼