g640 - 璽羽的壽司

🔗 前往 ZeroJudge 原題

題目描述

題目描述了璽羽經營一家壽司店，顧客會根據自己的預算購買盡可能高價的壽司。如果店內沒有符合預算的壽司，顧客會直接離開。題目要求計算璽羽賣出的壽司總價格。

解題思路

首先，將所有壽司的價格進行排序。對於每個顧客，使用二分搜尋查找價格大於或等於顧客預算的最低價格的壽司。如果找到符合條件的壽司，則將其價格加到總價格中。由於題目要求優先售出品質最差的壽司，而我們已經對壽司價格排序，因此使用 lower_bound 找到的壽司即為符合條件的最低價格壽司。

複雜度分析

• 時間複雜度: O(N log N + M log N)
  • 排序壽司價格需要 O(N log N) 的時間。
  • 對於每個顧客，二分搜尋需要 O(log N) 的時間，總共 M 個顧客，因此需要 O(M log N) 的時間。
• 空間複雜度: O(N)
  • 需要額外空間儲存壽司價格陣列。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
long long a[1000005],n,m,k,ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0;i<n;++i){
		cin >> a[i];
	}
	sort(a,a+n);
	for(int i=0;i<m;++i){
		cin >> k;
		ans+=*lower_bound(a,a+n,k);
	}
	cout << ans;
}