a253 - 王老先生的磨菇田

🔗 前往 ZeroJudge 原題

題目描述

題目描述了王老先生種植各種磨菇，並需要統計每種磨菇的數量。輸入包含磨菇的初始數量和之後增長的數量，最終需要按照磨菇的編號從小到大輸出每種磨菇的總數量（數量為0的不輸出）。

解題思路

這題主要考驗對輸入的處理和使用陣列進行統計的能力。程式使用一個大小為 101 的整數陣列 s 來儲存每種磨菇的數量，陣列的索引代表磨菇的編號。程式首先讀取初始的磨菇數量，然後讀取增長的磨菇數量，並將其加到對應編號的陣列元素中。讀取完所有輸入後，程式遍歷陣列，輸出數量不為 0 的磨菇編號和數量。

複雜度分析

• 時間複雜度: O(N + M)，其中 N 是初始磨菇種類的數量，M 是增長磨菇種類的數量。程式需要遍歷輸入資料兩次，以及遍歷陣列一次。
• 空間複雜度: O(1)，程式使用一個固定大小的陣列 s，空間複雜度為常數。

程式碼

#include <iostream>
using namespace std;
int s[101],n,a;
bool br=0;
int main(){
	while(cin >> a){
		if(a==-1){
			cin >> a ;
			if(a==-1){
				br=1;
				break;
			}
			else{
				cin >> n;
				s[a]+=n;
			}
		}
		else{
			cin >> n;
			s[a]+=n;
		}
		if(br==1){
			break;
		}
	}
	for(int i=0;i<101;i++){
		if(s[i]!=0){
			cout << i << " " << s[i] << "\n";
		}
	}
}