主題

ZeroJudge - f631: 同學會 解題心得

Not In My Back Yard | 2021-01-28 00:00:01 | 巴幣 2 | 人氣 45

題目連結:


題目大意:
輸入有多筆測試資料(≦ 100 筆),每筆佔三列。

測資第一列給定一正整數 N 、 M (1 ≦ N 、 M ≦ 10000),代表有 N 位學生以及 M 道菜。接著一列給定 N 個整數,代表有 N 位同學一開始身上各自帶的金錢量。最後一列給定 M 個整數,代表每一道菜應付的金額。

每有一道菜上來時,學生們會請目前最有錢的同學支付該道菜的費用。如果最有錢的同學金額不足以支付,則由第二有錢的同學支付剩下不足的,如果也不夠就找第三有錢的,以此類推。

試問:一開始最有錢的同學身上的金額量以及所有菜付完錢後最有錢的同學之金額量為何?如果有任何一道菜上來時,所有同學的金錢總額不足以支付該道菜,則改為輸出「Oh My God」。



範例輸入:
3 4
100 200 300
200 200 200 200
5 7
1500 1500 1000 2000 3000
900 600 200 350 1200 400 1000


範例輸出:
Oh My God
3000 1450


解題思維:
使用優先佇列(Priority Queue,以前的題目有稍微提及過)模擬即可。

首先將所有同學身上的金額丟進宣告的優先佇列 P 裡,此時 P 的頂端(因為本質是堆積(Heap),所以有著「頂端」此概念)預設存的就是金額量最大的值。

接著依序掃過每一道應支付的金額 C,從 P 中取出頂端之值 M,判斷 C 與 M 之大小。如果 C < M ,則代表該位同學還綽綽有餘,將 M 之值減去 C 之後放回 P 中;當 C = M 時,代表該名同學剛好沒錢了,所以付完之後也不用再次放回 P 中(因為真的沒錢了);當 C > M 時,該同學不只沒錢還不夠付,所以又要從 P 中拿取頂端元素,並將 C 減去 M 然後重複前面的步驟。

如果在支付的過程中,有任何時刻 P 取到為空且目前的菜之金額 C > 0,則代表所有同學已經沒錢可以付剩下的菜餚了,因此輸出「Oh My God」;反之,如果完全沒事的話,則輸出一開始 P 的頂端元素以及最後 P 的頂端元素之值即是所求。




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

創作回應

更多創作