不能寫C++麼?只用C寫這個不是不行,但沒了STL和封裝寫起來會略DT。
我們能拿到每頭牛每天的奶量,並且必須存下來,所以輸入就是每頭牛每天的奶量。
額外的輸出還有三樣:一是每週總奶量最多的牛;而是每週有四天奶量低於12升的牛;三是牛群的總產奶量。
一和三都需要知道每頭牛每週的總奶量,我們可以用連結串列維護每頭牛每天的奶量,以方便去除最早一天的奶量記錄,並加上最近一天的奶量記錄(滑動視窗)。這樣給每頭牛加上一個無符號整型(如果用分升做單位),我們可以知道O(1)時間更新每頭牛每週的總奶量,再加上一個整型記錄牛群總奶量,就能得到三。在每天更新的時候按照陣列找最大數的演算法就能找到過去7天內產奶量最多的牛隻,就能得到一。
對於二,我們可以給每頭牛再加一個整型用來記錄過去7天內奶量低於12升的天數,在每次更新的時候按照彈出和加入的資料做加減,就能夠O(1)時間更新它。然後在再根據每天更新的情況額外用一個集合型別維護滿足條件的牛隻編號集合就OK了。
最後,我們把牛隻的資料存放於一個從編號到結構體的雜湊表中,就能做到O(1)查找了。
這種程式碼還是自己寫比較好。
不能寫C++麼?只用C寫這個不是不行,但沒了STL和封裝寫起來會略DT。
我們能拿到每頭牛每天的奶量,並且必須存下來,所以輸入就是每頭牛每天的奶量。
額外的輸出還有三樣:一是每週總奶量最多的牛;而是每週有四天奶量低於12升的牛;三是牛群的總產奶量。
一和三都需要知道每頭牛每週的總奶量,我們可以用連結串列維護每頭牛每天的奶量,以方便去除最早一天的奶量記錄,並加上最近一天的奶量記錄(滑動視窗)。這樣給每頭牛加上一個無符號整型(如果用分升做單位),我們可以知道O(1)時間更新每頭牛每週的總奶量,再加上一個整型記錄牛群總奶量,就能得到三。在每天更新的時候按照陣列找最大數的演算法就能找到過去7天內產奶量最多的牛隻,就能得到一。
對於二,我們可以給每頭牛再加一個整型用來記錄過去7天內奶量低於12升的天數,在每次更新的時候按照彈出和加入的資料做加減,就能夠O(1)時間更新它。然後在再根據每天更新的情況額外用一個集合型別維護滿足條件的牛隻編號集合就OK了。
最後,我們把牛隻的資料存放於一個從編號到結構體的雜湊表中,就能做到O(1)查找了。
這種程式碼還是自己寫比較好。