python-APCS-2023/1/8實作第四題:機器出租
===
### ZeroJudge:j608機器出租
#### 沒有圖解，請耐心閱讀，感恩
---
\
\
\
\
\
<font color="#FFEE99">**1超時問題與40分思考想法**</font>
---
:::info
**超時問題**
在20分測資中基本上是沒有超時問題
40分測資開始，只能用1次且單層迴圈搜尋整個活動的資料，否則會超時
\
**40分思考想法**
在活動時間中，要不重複拿取時間段，且要拿到最佳的方法
既然要一個個拿，那就必須要排序，而問題就在如何排序
\
從結論來看-->結論是必須依照每個活動的結束時間排序
原因:
整個活動時間內有一堆互相重疊的線段[頭, 尾]
把所有互相重疊的線段拿來看-->選了其中一個，剩下的都不能選了
\
假設有以下線段:[[1, 3], [2, 4], [3, 4], [3, 5], [5, 6], [2, 7], [4, 7], [7, 8]]:已排序
從第一個拿[1, 3], 其他的線段的尾一定>=3
跟[1, 3]重複的線段:
尾=3那一定重疊
尾>3如果重疊，那一定是頭<=3才會碰到[1, 3]線段
因此跟[1, 3]重疊的線段都有一個共通點:線段都碰到3
所以他們是互相重疊的，而到底該選哪個?
以下是重疊的線段
[1, 3]影響有碰到3以下的數字
[2, 4]影響有碰到4以下的數字
[3, 4]影響有碰到4以下的數字
[3, 5]影響有碰到5以下的數字
[2, 7]影響有碰到7以下的數字
如果你拿了[2, 4]那麼有可能就會影響到後面本來可以拿的[4, 7]
尾越小的線段影響得越少-->按照尾來排的話，第一個必拿
從這裡可以得到一個邏輯:我從第一個開始拿[1, 3]，並且後面開始，線段只要頭碰到3以下，我都不能拿，直到再找到可以拿的線段[5, 6]，從這裡開始，線段頭碰到6以下，我都不能拿，以此類推
:::
:::success
**二維list的排序**
參考來源:https://docs.python.org/3/howto/sorting.html
或者搜尋python org，在裡面找到sort的章節
\
總之就是使用operator模組中的itemgetter
list.sort()中有key和reverse，你就把key想成排列的依據，key=itemgetter(num1, num2)的意思是:按照list中索引num1小到大排列，如果相等，再用num2排列...
\
**zip()用法**
zip(list1, list2)
會回傳
[(list1[0], list2[0]), (list1[1], list2[1])... ...]
其中()是turtle型別
:::
程式碼line8:
activities存放所有時間資料
choose記錄拿的次數
limit記錄每次拿完後的尾

from operator import itemgetter

n, k = map(int, input().split())
s = [int(i) for i in input().split()]
f = [int(i) for i in input().split()]
activities = [list(i) for i in (zip(s, f))]
s = f = None
activities.sort(key=itemgetter(1))
choose = 0
limit = -1
for i, j in activities:
    if i > limit:
        choose += 1
        limit = j
print(choose)

\
\
\
<font color="#FFEE99">**2滿分解法**</font>
---
:::info
**滿分思考**
從40分解法我們知道一個概念:拿完線段後，limit存放下一個可拿線段的限制
而當有多個機器的話，當然就是存放每一個機器的limit
\
假設兩臺機器-->開始搜尋，只要有機器可以拿搜尋到的線段，就拿
問題:如果兩個機器都可以拿這個線段怎麼辦?
假設目前limit分別是1和5並且有一個線段[6, 10]頭都比limit大
\
如果這個時候配給限制是1的線段會發生什麼事?
-->配置給limit=1的機器後limit變成10和5
-->配置給limit=5的機器後limit變成1和10
看得出來後者的limit會比較不嚴格
\
結論:找出通過限制的線段後，把它配置目前給limit最大的機器
\
**找出頭應該給哪個機器**
limit = [1, 9, 8, 3, 5, 6]
線段[6, 10]
首先:把6放入limit並且limit.sort(reverse=True)
limit = [9, 8, 6, 6, 5, 3, 1]
找出6的索引-->index=2
**找出小於6的limit值-->index = 2+limit.count(6)-->5(找到了!!)**
取線段並且改變limit值
limit = [9, 8, 6, 6, 6, 3, 1]
將放入的頭拿出
limit.pop(limit.index(6))
limit = [9, 8, 6, 6, 3, 1]
:::
註:我的寫法是用很簡單的寫法但複雜邏輯操作，很吃理解
\
程式碼:

from operator import itemgetter

n, k = map(int, input().split())
s = [int(i) for i in input().split()]
f = [int(i) for i in input().split()]
activities = [list(i) for i in (zip(s, f))]
s = f = None
activities.sort(key=itemgetter(1))
limit = [-1] * k  # 存放所有機器的限制(哪一個機器的不重要)
choose = 0
for i, j in activities:
    limit.append(i)
# 暫時先把i放到機器中並用line13的sort搭配.index()找出相對位置
    limit.sort(reverse=True)  # 由大到小
    if i != limit[-1]:  # 如果i的位置在最後面，代表他沒有通過所有機器的限制
        choose += 1
        limit[limit.index(i)+1+limit.count(i)-1] = j
# 在沒有重複下i的下一個就是通過的limit
# 但如果有重複的話ex.[5, 5, 4, 3] i = 5
# 5的下一個還是5，所以line17才會再加上limit.count(i)-1
    limit.pop(limit.index(i))  # 把暫時放入的i拿出去
print(choose)


###### tags: `題解`
###### tags: `APCS`
###### tags: `python`