b035: 電皇的資源回收場
Tags : gp_hash_table map pbds unordered_map
Accepted rate : 19人/25人 ( 76% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-15 11:13

Content

 本題出自 YTP 2019 初賽 p. 3

電皇思朋是一位又帥又電的有錢人,不過他有個奇怪的癖好,在他專屬的回收場中收集資源。電皇專屬資源回收場在金銀河的上游,從黃金馬桶、到可回收塑膠都有。由於他收集的回收資源太多了,電皇思朋想要辦一個回收資源拍賣會,並推出各種組合。任意兩個回收資源加起來的價值等於  $ V $ ,計算出對每一個 $ V $ 有多少種優惠組合。請你幫忙寫一支程式計算。

Input

第一行為一個正整數 $ N $ ,代表總共有幾個需要拍賣的回收資源。

第二行開始有 $ N $ 個整數 $ a_i $ ,代表每個回收資源的價值。

接下來有一個整數 $ V $ 。

$$ 1 \leq N \leq 10^6, 0 \leq a_i \leq 10^6, -2^{31} \leq V \leq 2^{31} - 1 $$

Output

對於 $ V $ 輸出一行正整數,表示對於多少組 $ (i,  j) $ 使得 $ i < j, a_i + a_j = V $ 。

Sample Input #1
6
1 2 3 4 5 0
6
Sample Output #1
2
Sample Input #2
10
1 2 1 2 4 4 3 3 3 2
4
Sample Output #2
9
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (6%): 1.0s , <1K
公開 測資點#1 (6%): 1.0s , <1M
公開 測資點#2 (6%): 1.0s , <1M
公開 測資點#3 (6%): 1.0s , <1M
公開 測資點#4 (6%): 1.0s , <1M
公開 測資點#5 (7%): 0.6666666666666666s , <1M
公開 測資點#6 (7%): 0.6666666666666666s , <1M
公開 測資點#7 (7%): 0.6666666666666666s , <1M
公開 測資點#8 (7%): 0.6666666666666666s , <1M
公開 測資點#9 (7%): 0.6666666666666666s , <1M
公開 測資點#10 (7%): 0.6666666666666666s , <1M
公開 測資點#11 (7%): 0.6666666666666666s , <1M
公開 測資點#12 (7%): 0.6666666666666666s , <1M
公開 測資點#13 (7%): 0.6666666666666666s , <1M
公開 測資點#14 (7%): 0.6666666666666666s , <1M
Hint :

$a_i$, $V$ 都有可能為 $0$

Tags:
gp_hash_table map pbds unordered_map
出處:
YTP 2019 Pre [管理者:
nevikw39 ($\mathscr{nevikw}\pmb{39}\in\mathbf{37}^{th}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」