一、題目
有n 把鑰匙，m 個鎖，每把鎖只能由一把特定的鑰匙打開，其他鑰匙都無法打開。一把鑰匙可能可以打開多把鎖，鑰匙也可以重復使用。 對于任意一把鎖來說，打開它的鑰匙是哪一把是等概率的。但你無法事先知道是哪一把鑰匙，只能進行嘗試。 已知每次嘗試用第i把鑰匙打開第j把鎖會消耗的時間a ij 秒。 問最優策略下打開所有鎖的總期望時間是多少秒。
輸入描述?第一行兩個以空格分隔的正整數n,m。 接下來m行每行m個空格分隔的正整數aij。 1<=n,m,aij <=500
輸出描述?輸出一個小數代表答案，你的答案會被認為是正確的當且僅當你的答案與正確答案的絕對誤差或相對誤差不超過10-6。
二、分析
這個問題涉及到尋找一種最優策略以最小化在平均情況下打開所有鎖所需的總時間。具體來說，我們有n把鑰匙和m個鎖，每把鎖由且僅由一把特定的鑰匙打開，但每把鑰匙可能用于打開多把鎖。我們無法事先知道哪把鑰匙能打開哪把鎖，只能通過嘗試來確定。每次嘗試用鑰匙i打開鎖j會消耗時間a_ij秒。我們的目標是在最優策略下計算打開所有鎖的總期望時間。這個問題可以通過為每個鎖單獨尋找最優的鑰匙嘗試順序來解決。由于每個鎖的正確鑰匙是等概率分布的，每個鎖的處理可以獨立進行。對于每個鎖來說，最優的策略是按鑰匙的嘗試時間從小到大進行排序，這樣的順序能最小化期望時間。
對于每個鎖，正確鑰匙的位置是均勻分布的，因此期望時間可以通過加權和來計算，其中每個鑰匙的權重是其在嘗試順序中的位置。具體來說，對于每個鎖j，我們對鑰匙按a_ij從小到大排序，然后計算排序后的加權和，其中第i小的鑰匙的權重為n-i+1（即從n到1遞減）。總期望時間是所有鎖的加權和的平均值，即所有鎖的加權和相加后除以n。首先讀取輸入的n和m，然后讀取每個鎖對應的n個嘗試時間。對于每個鎖，對嘗試時間進行排序，然后計算加權和。最后，將所有鎖的加權和相加，并除以n得到總期望時間。代碼實現中，我們首先讀取輸入數據，然后對每個鎖的嘗試時間進行排序，計算每個鎖的加權和，最后累加所有鎖的加權和并除以n得到結果。這個方法有效地利用了貪心策略，確保每個鎖的處理都是最優的，從而使得總期望時間最小化。
具體來說，對于每把鎖j，將它的n個嘗試時間a_ij進行升序排序。然后計算排序后的加權和，即第i小的時間乘以權重(n-i+1)，并將所有鎖的加權和累加起來，最后除以n得到總期望時間。這種方法確保了每個鎖的處理都是最優的，從而整體上最小化了期望時間。
三、代碼
算法步驟
-
輸入處理：讀取n（鑰匙數）和m（鎖數），以及每個鎖對應的n個嘗試時間。
-
排序：對每個鎖的嘗試時間進行升序排序。
-
加權和計算：對排序后的每個鎖，計算加權和，其中權重從n到1遞減。
-
總期望時間：將所有鎖的加權和相加后除以n，得到總期望時間。
def main():import sysinput = sys.stdin.read().split()ptr = 0T = int(input[ptr])ptr += 1for _ in range(T):t = int(input[ptr])ptr += 1state = list(map(float, input[ptr:ptr+3]))ptr += 3P = []for i in range(3):row = list(map(float, input[ptr:ptr+3]))P.append(row)ptr += 3current_state = state.copy()for _ in range(t-1):new_state = [0.0]*3for j in range(3):for k in range(3):new_state[j] += current_state[k] * P[k][j]current_state = new_stateif current_state[2] > 0.5:print(1)else:print(0)if __name__ == "__main__":main()-
輸入處理：讀取鑰匙數n和鎖數m，以及每個鎖對應的n個嘗試時間。排序：對每個鎖的嘗試時間進行排序，確保較小的時間排在前面。加權和計算：每個鑰匙的嘗試時間乘以其權重（從n到1），累加得到該鎖的總加權和。總期望時間：所有鎖的加權和相加后除以n，得到最優策略下的總期望時間。
通過這種方法，我們確保每個鎖的處理都是最優的，從而最小化總期望時間。
