題目連結:
題目大意:
輸入第一列給定兩正整數 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 元。
將所有賣出的壽司之品質加總即為所求。
不過因為測資輸入量有點大,因此需要最佳化輸出入。簡單的即可,如
這題。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。