f819 - 圖書館 (Library)

🔗 前往 ZeroJudge 原題

題目描述

題目描述了圖書館的借閱情況。對於每一筆借閱紀錄，包含借閱書籍的編號 m 和借閱天數 d。如果借閱天數超過 100 天，則需要支付罰款，罰款金額為 (借閱天數 - 100) * 5。題目要求計算總罰款金額，並輸出所有需要支付罰款的書籍編號，按照編號升序排列。

解題思路

解題思路是遍歷每一筆借閱紀錄，判斷借閱天數是否超過 100 天。如果超過，則計算罰款金額並累加到總罰款中，同時將書籍編號存儲到一個數組中。最後，對書籍編號數組進行排序，並輸出排序後的書籍編號和總罰款金額。使用了貪心策略，直接計算超過天數的罰款，並儲存需要輸出的書籍編號。

複雜度分析

• 時間複雜度: O(n log n)，其中 n 是借閱紀錄的數量。主要時間花費在排序書籍編號數組上。
• 空間複雜度: O(n)，其中 n 是需要支付罰款的借閱紀錄數量。主要空間花費在儲存書籍編號數組上。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int ans,n,m,d,a[2001],it;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> m >> d;
		if(d>100){
			ans+=(d-100)*5;
			a[it++]=m;
		}
	}
	sort(a,a+it);
	for(int i=0;i<it;++i){
		cout << a[i] << " ";
		if(i==it-1)cout << "\n";
	}
	cout << ans;
}