e541 - 10474 - Where is the marble

🔗 前往 ZeroJudge 原題

題目描述

題目描述了Raju和Meena玩大理石的遊戲。Raju按照數字升序放置大理石，Meena詢問特定數字的大理石位置。程式需要模擬這個過程，並輸出查詢結果。如果找到指定數字的大理石，輸出其位置；否則，輸出 "not found"。

解題思路

這題的解題思路是使用一個陣列來記錄每個數字的大理石數量。首先，讀取大理石的數量N和查詢的數量Q。然後，讀取N個大理石的數字，並將它們的數量記錄在陣列中。對於每個查詢，檢查陣列中是否存在該數字。如果存在，計算該數字的大理石的位置，並輸出結果。如果不存在，輸出 "not found"。位置的計算方式是累加小於等於該數字的所有大理石數量。

複雜度分析

• 時間複雜度: O(N + Q * M)，其中 N 是大理石的數量，Q 是查詢的數量，M 是大理石數字的最大值 (10000)。因為需要遍歷所有大理石來初始化陣列，並且對於每個查詢，需要計算位置，這需要遍歷到查詢數字。
• 空間複雜度: O(M)，其中 M 是大理石數字的最大值 (10000)。因為需要一個陣列來記錄每個數字的大理石數量。

程式碼

#include <iostream>
using namespace std;
int n[10001];
int main(){
	int a,b,c=0,k;
	while(cin >> a >> b){
		if(a==0&&b==0)break;
		for(int i=0;i<10001;++i)
			n[i]=0;
		while(a--){
			cin >> k;
			n[k]++;
		}		
		cout << "CASE# " << ++c << ":\n";
		while(b--){
			cin >> k;
			if(n[k]==0)
				cout << k << " not found\n";
			else{
				int ans=1;
				for(int i=0;i<k;++i)
					ans+=n[i];
				cout << k << " found at " << ans << "\n";
			} 	
		}
	}
}