Spring Practices 01 心得&題解

<<回主頁

前言

因為是學校練習用的，不知道題目能不能公開，但還是寫個心得好了。

這次還是用以前常用的 Java，題目的 io 方式不是很習慣，所以就不敢用沒有很熟的 C++ 練習了 (下次一定)。

覺得自己太久沒打比賽有點太緊張。

總共有五題，編號 A~E，以下照 AC 順序:

pA

這題看起來是一個裸題，甚至在 AP325 做過，就是一個 greedy 的題目，只是這次套上三角函數的 function 叫你自己生成。

解法就是從左掃到右不斷記得目前的最高點，然後去跟之後的點相減，最後取最大的，時間複雜度

$O(n)$，空間可以壓到

$O(1)$。

pC

看到 bin packing 瞬間嚇毛了 (以為是可以一個 bin 塞很多東西的)，還好一個最多只能塞兩個。

那就先排序然後左右拿兩個指標去掃，目標是先放最大的那邊，那最小的那邊看可不可以放進去，可以就順便放吧!

時間複雜度

$O(nlogn)$，空間

$O(n)$。

忘記處理掃到同一個的情況(我本來程式會多 +1) orz

pD

這題題目看起來很複雜，但簡單題敘就是 :

給你

$n$ 個選項，第

$i$ 個你會獲得

$y_i$ 元又同時失去

$x_i$ 元，你發現有些選項很爛，你可以最多不選擇其中

$k$ 個。

那很顯然我們可以壓縮成 :

給你

$n$ 個選項，第

$i$ 個你會獲得

$y_i-x_i$ 元，你可以最多不選擇其中

$k$ 個。

我們可以把

$y_i-x_i$ 排序，對於前

$k$ 小的如果是負的就不選，後面不管怎樣都選，然後沒開 long long 會 overflow。

時間複雜度

$O(nlogn)$

pE

可以先想另一題 : 如果一天最多能走

$x$ 公里，那要幾天走完，這顯然就是 greedy，每天盡量走遠就可以

$O(n)$ 解決的。

那套到這題可以二分搜答案!

因為要搜

$logC$ 次 (其中

$C$ 是 值域

$\times n$)，所以時間複雜度是

$O(nlogC)$

起初被 EOF 問題弄到 (太久沒寫)
然後

$k$ 忘記加一，一開始以為是題目搞我不寫範圍， int 不夠大 (這麼能走的嗎 ?) 還在那改型別，賽後 2 分才 AC

pB

賽中寫完 A 看到這我覺得可能是要我構造解決方法之類的題目 (沒仔細看)，想說好像很噁就丟掉了，有空再回來看然後就沒空了

其實就只是模擬題，後來終於把他補掉了

有幾個覺得個人採到雷的地方:

1. 指令居然不是一個測資一排，我一開始看以為是，直到寫好範測跑出來怪怪的才發現。然後因為這個性質，就算你踩到錯誤的指令，還是要乖乖跑完(你可以不繼續做操作)，因為你不知道指令終點在哪。

2. 空格在最後的狀況，不知道是不是複製貼上還是他本來測資也有這個問題，我是一行一行讀，你讀入的時候會只讀到 4 個字(而不是 4 個字 + 空格)，然後你就可能會戳到陣列外的東西，還好範測有，不然我是覺得我找不出來。