d716. Unique Snowflakes(強化版) - 高中生程式解題系統

內容

企業家 Emily 有一個很酷的生意點子：包裝並販賣雪花。她開發了一個機器，可以在雪花飄落時把它們補捉下來，送入一個雪花流並一個一個地注入包裝盒中。一旦盒子滿了，便封起來並運出去賣。

這公司的行銷口號為「獨特滿囊」。為了實踐這個口號，包裝盒中的每一片雪花都必須彼此相異。這說得容易，事實上，機器上流的雪花有很多是相同的。Emily 想知道最大包的相異雪花可以有多大包。機器可以在任何時候開始打包，一旦開始打包，線上的雪花都必須進入盒中直到盒子填裝完畢並封起來。隨時可以封包裝盒，不用等所有的雪花都流出機器之後才封。

輸入說明

輸入的第一行有一個整數代表以下有幾組測試資料。每組測試的第一行含有一個整數 n，代表機器處理的雪花數量。接下來的 n 行每行有一個整數 (範圍為 0 to 10^9 (含)) 分別代表一片雪花。只有當兩片雪花相同時，他們的號碼才會相同。輸入檔不會有超過一百萬片雪花。

輸出說明

對於每組測試請輸出含有一個整數的一行，代表盒中最多可以有幾個彼此相異的雪花。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (10%): 1.0s , <1M
公開測資點#1 (25%): 3.0s , <10M
公開測資點#2 (25%): 3.0s , <10M
公開測資點#3 (40%): 3.0s , <10M

提示：

鑒於d194: 11572 - Unique Snowflakes 的測資有點弱 ( O(n^2)就能過了! )

這裡的n是真的會到1000000 !

※優化輸入會比較快，但不影響通過與否 (java我就不確定了..)

※我自己有些程式能在Uva通過但在此題WA，那是Uva的測資比較弱(沒有測到盲點)

當然如果懷疑測資有誤歡迎通知

※HASH、AVLTree、quicksort+binarysearch

標籤:

出處:

UVa 11572 加強版 [管理者： david942j (文旋) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」