g796 - 檔案分類 (Files)

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取 n 個檔案名稱，每個檔案名稱是一個整數。檔案名稱的分類規則是取檔案名稱除以 1000 的餘數，再除以 10 的整數部分。例如，檔案名稱 32 時，分類為 (32 % 1000) / 10 = 3。最後，輸出每個分類的檔案數量，按照分類編號從小到大排序。

解題思路

這題的核心是將檔案名稱進行分類，並統計每個分類的檔案數量。由於檔案名稱是整數，我們可以利用取模運算和整數除法來計算檔案的分類編號。使用一個陣列 c 來儲存每個分類的檔案數量，陣列的索引代表分類編號，陣列的值代表該分類的檔案數量。讀取檔案名稱後，根據分類編號更新 c 陣列。最後，遍歷 c 陣列，輸出非零的分類編號和其對應的檔案數量。

複雜度分析

• 時間複雜度: O(n + k)，其中 n 是檔案數量，k 是分類的數量 (在本題中 k=101)。讀取檔案需要 O(n) 時間，統計檔案數量需要 O(n) 時間，輸出結果需要 O(k) 時間。
• 空間複雜度: O(k)，其中 k 是分類的數量 (在本題中 k=101)。需要一個大小為 k 的陣列 c 來儲存每個分類的檔案數量。

程式碼

#include <iostream>
using namespace std;
int n,c[105],x;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> x;
		c[(x%1000)/10]++;
	}
	for(int i=0;i<101;++i){
		if(c[i]){
			cout << i << " " << c[i] << "\n";
		}
	}
}