程式設計與實踐第三次題目
- T11
- Description
- 思路
- T12
- Description
- 思路
- T13
- Description
- 思路
- T14
- Description
- 思路
- T15
- Description
- 思路
樂學服務器炸掉了還剩個11沒A，趕快過來寫題解QWQ
T11
Description
小張在玩一種卡牌游戲，牌組由 2n 張牌組成，其中 n 張上寫有數字 1…n 各一張，其余 n 張上全部是數字 0 ，
現在牌組經過隨機打亂后，小張拿走其中 n 張牌作為手牌，其余 n 張牌作為牌堆，
小張想經過若干次如下操作使得牌堆自頂向下的牌依次為 1…n ，
每一次操作，小張選擇任意一張手牌放到牌堆底，并將牌堆頂的牌放入手牌，
他想知道最少進行幾次操作，使得牌堆自頂向下的牌依次為 1…n ，
思路
啊這 我好菜還沒做 馬上會補上的！
T12
Description
小張在暑假時間來到工地搬磚掙錢，包工頭交給他一項艱巨的任務，將一排磚頭按照從低到高的順序排好，可是小張的力量有限，每次只能交換相鄰的兩塊磚頭，請問他最少交換幾次能夠完成任務？
思路
其實可以直接套歸并排序的模板然后輸出逆序數，具體原理也會馬上補上，QWQ
T13
Description
小張經常為了事情太多安排不開而苦惱，現在他手頭有 n 項任務，每項任務都有一個開始時間 s_i 和結束時間 e_i ，要想完成一個任務必須從開始時間做到結束時間，并且同一時間小張只能進行一項任務，
小張想知道他最多可以完成幾項任務，
思路
方法是，對結束的時間進行排序，然后去從第一個節目開始比對，如果這個節目的結束時間小于等于下一個開始時間，那就可以看，計數器+1即可，
T14
Description
和許多同齡女孩子一樣，久蓮也喜歡水晶球，
還有 10 天，就是心心念念的他生日了，
久蓮希望把全世界最大最好看的水晶球送給他，
她找到了寶石收藏家亞瑟斯，希望能夠尋求他的幫助，
亞瑟斯很快被打動了，拿出了精心收集的 n 塊美麗的水晶石，這些水晶石初始是長寬高分別為 a 逗號 空格 b 逗號 空格 c 的長方體，亞瑟斯許諾久蓮可以從中取走 1 塊水晶石作為她禮物的原材料，
同時亞瑟斯有一種魔法，如果這兩塊長方形水晶石在某一個面能夠完美的契合在一起（完美的契合是指這兩個長方形面全等），那么可以將它們融合成一塊完整的大石頭，如果真的實作的話，那么久蓮就可能打磨出更大的水晶球啦！
久蓮太希望把最美最大的水晶球送給他了，你快幫幫她如何選擇吧，
思路
本題的目的是：找所有（不管是單個方塊還是組合過的）的最短邊（最小值）的最大值，
對于一個長方體，能切出來的球的直徑最大值取決于長方體的最短邊長度，
這道題可能一開始直接的想法是二重回圈遍歷所有組合，然后組合里面再去交叉比對是否匹配，但是這必定TLE
其中有四個優化點：
- 輸入的時候要給每個方塊長寬高排序，得到最長邊max，中邊mid，最短邊min，這樣會很方便之后去處理這些資料，
- 判斷兩個方塊是否匹配的時候不用交叉比對，因為我們在第一步已經排好序了，只用比較兩個方塊的mid和max是否分別相等，如果不相等即使匹配了也沒有意義，原因在于假如兩個方塊融合了，會得到一個邊長為：匹配邊1，匹配邊2，非匹配邊之和的方塊，如果不是mid和max分別相等，而是min參與了匹配，那么min會被保留下來，也意味著這兩個塊的融合沒有給整體帶來任何優化，因為最短邊還在，
- 對每組max, mid, min排序，依照max從小到大（從大到小），如果max相等則mid從小到大（從大到小），如果mid相等則min從小到大（從大到小）的順序排序，（我還不確定這個是否有用，待會樂學如果修好了我去試一試）（因為我一開始是按著排序后只用看相鄰去做的，但是wa了2/17）
- 最后還是要遍歷所有組合，此處一定要加上一個判斷，如果其中一個塊的mid<=當前找到的最大值，直接continue，否則后幾個用例會TLE，因為如果匹配上了，更新最短邊的公式是新的最小值的最大值（結果） = min（a1+a2,b1），所以只要mid小于當前找到的最小值的最大值（結果）直接pass掉就行，
然后，建議使用long long，免得血壓因為這個突然上升
T15
Description
在這款游戲中，每一條惡龍有一個難度值 x_i 和一個經驗值 y_i ，游戲中的英雄具有攻擊力 A ，游戲一開始英雄的攻擊力 A=0 ，打到一條惡龍你的攻擊力需要大于難度值 x_i ，在你擊敗惡龍以后，你的攻擊力會增加經驗值 y_i ，
當然，你有時需要額外提升你的攻擊力，此時你只需氪金1元，就能增長一點攻擊力，小張想知道，如果他自己決定挑戰惡龍的順序，要想擊敗所有惡龍至少需要氪金多少錢？
思路
貪就要貪個痛快，先打經驗值是正的的龍，然后打經驗值是負的的龍，
對于經驗值是正的的龍，按照等級從小到大排序挨著打，如果等級不夠就氪金，
對于經驗值是負的的龍，按照等級+經驗值從大到小排序挨著打，如果等級不夠就氪金，
思路就是這樣，
然后，還是建議使用long long，免得血壓因為這個突然上升
趕快去寫T11和T12的題解QWQ
希望樂學沒事( ?? ω ?? )?
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79001.html
標籤：其他
下一篇：Vue 路由跳轉至外界頁面