ETH官方钱包

前往
大廳
主題

ZeroJudge - g640: 璽羽的壽司 解題心得

Not In My Back Yard | 2021-12-12 00:00:01 | 巴幣 0 | 人氣 368

題目連結:


題目大意:
輸入第一列給定兩正整數 N 、 M(N 、 M ≦ 10 ^ 6),代表有 N 種壽司以及 M 位顧客。接著第二列給定 N 個正整數(皆小於 2 ^ 31),代表每種壽司的價錢,同時也是壽司的品質。最後第三列給定 M 個正整數(皆小於 2 ^ 31),代表每個顧客所能接受的最低品質。

由於品質越好越難製作,因此璽羽只會賣出盡可能低品質的壽司。因此璽羽只會賣給每個顧客在他們能接受的情況下最低品質之壽司,而如果顧客的最低標準大於店內所有壽司的品質,則該顧客會自行離開不會消費。

試問,璽羽總共賣出了多少錢的壽司?



範例輸入:
5 4
4 2 8 10 12
3 15 11 4


範例輸出:
20


解題思維:
先將壽司的品質(即價格)由小排到大(大排到小也可以),接著對於每位顧客的最低標準利用二分搜尋法(Binary Search)去找大於等於該標準且為最小者即可。如果該顧客的最低標準大於所有壽司的品質,則忽略(如題意所述);反之,則璽羽將會賣該種壽司(假設品質為 T)給現在這位顧客,因此賺得 T 元。

將所有賣出的壽司之品質加總即為所求。

不過因為測資輸入量有點大,因此需要最佳化輸出入。簡單的即可,如這題



本人的程式碼(放在 HackMD)https://hackmd.io/@Inversionpeter/B137YIwuY

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創(chuàng)作回應

更多創(chuàng)作