ZeroJudge 解題筆記：g640. 璽羽的壽司

作者：王一哲
日期：2025年11月9日


ZeroJudge 題目連結：g640. 璽羽的壽司

解題想法

因為壽司沒有限量，可以重複賣出同樣價格的壽司，所以只要先將所有的壽司價格由小到大排序，再用二分搜尋法從所有壽司價格找等於顧客標準或是大於標準且最接近的值。

Python 程式碼

使用時間約為 4 s，記憶體約為 213.6 MB，通過測試。

from bisect import bisect_left

n, m = map(int, input().split())
arr = sorted(list(map(int, input().split())))
tot = 0
for b in map(int, input().split()):
    idx = bisect_left(arr, b)
    if idx == n: continue
    tot += arr[idx]
print(tot)

C++ 程式碼

使用時間約為 0.4 s，記憶體約為 4.1 MB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
typedef unsigned long long LL;
using namespace std;

int main() {
    int n, m; scanf("%d %d", &n, &m);
    vector<int> arr (n);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    sort(arr.begin(), arr.end());
    LL tot = 0;
    for(int i=0, b; i<m; i++) {
        scanf("%d", &b);
        auto it = lower_bound(arr.begin(), arr.end(), b);
        if (it == arr.end()) continue;
        tot += *it;
    }
    printf("%lld\n", tot);
    return 0;
}