a556: multiset 應用
標籤 : binary search
通過比率 : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-11-18 20:24

內容

有 $n$ 張演唱會票,每張票都有一個特定的價格。接著,$m$ 位顧客依次到來。

每位顧客會宣布他們願意支付的最大價格,然後他們將會獲得一張與其最大價格最接近的票,並且這張票的價格不會超過該顧客的最大價格。

請注意人會按照順序來

  • $1 \le n, m \le 2 \cdot 10^5$
  • $1 \le h_i, t_i \le 10^9$
輸入說明

第一行輸入兩個整數 $n$ 和 $m$:票的數量和顧客的數量。
第二行輸入 $n$ 個整數 $h_1$, $h_2$, ..., $h_n$:每張票的價格。
最後一行輸入 $m$ 個整數 $t_1$, $t_2$, ..., $t_m$:每位顧客的最大支付價格(按照顧客到達的順序)。

輸出說明

對於每位顧客,輸出他們會支付的票價。如果顧客無法購得票,則輸出 -1。
每張票只能被購買一次。

範例輸入 #1
5 3
5 3 7 8 5
4 8 3
範例輸出 #1
3
8
-1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <1K
提示 :
標籤:
binary search
出處:
cses [管理者:
haha (大學長)
]


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