d716. Unique Snowflakes(強化版)
標籤 :
通過比率 : 138人/169人 ( 82% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-06-15 20:56

內容

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

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

輸入說明
輸入的第一行有一個整數代表以下有幾組測試資料。每組測試的第一行含有一個整數 n,代表機器處理的雪花數量。接下來的 n 行每行有一個整數 (範圍為 0 to 10^9 (含)) 分別代表一片雪花。只有當兩片雪花相同時,他們的號碼才會相同。輸入檔不會有超過一百萬片雪花。
輸出說明
對於每組測試請輸出含有一個整數的一行,代表盒中最多可以有幾個彼此相異的雪花。
範例輸入 #1
1
5
1
2
3
2
1
範例輸出 #1
3
測資資訊:
記憶體限制: 512 MB
提示 :

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

這裡的n是真的會到1000000 !

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

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

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

※HASH、AVLTree、quicksort+binarysearch

標籤:
出處:
UVa11572加強版 [管理者: david942j (文旋) ]

本題狀況 本題討論 排行

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