e196 - 又是進德教育

🔗 前往 ZeroJudge 原題

題目描述

題目描述了板橋高中進德教育的簽名制度。每個學生需要簽名兩次才能完成進德流程。題目要求讀取學生的簽名紀錄，統計有多少學生沒有完成進德流程，也就是說，簽名次數少於兩次的學生數量。

解題思路

這題的解題思路很直接。首先，讀取學生總數 m 和簽名紀錄的數量 n。然後，建立一個大小為 m 的陣列 a，用於記錄每個學生的簽名次數。接著，讀取 n 個簽名紀錄，對於每個紀錄，將對應學生的簽名次數加一。最後，遍歷陣列 a，統計簽名次數少於兩次的學生數量，並輸出結果。

複雜度分析

• 時間複雜度: O(n + m)，其中 n 是簽名紀錄的數量，m 是學生總數。
• 空間複雜度: O(m)，用於儲存每個學生的簽名次數。

程式碼

#include <stdio.h>
int main(){
	int m,n;
	while(scanf("%d%d",&m,&n)>0){
		int a[m]={0},k;
		while(n--){
			scanf("%d",&k);
			a[k-1]++;
		}
		k=0;
		for(int i=0;i<m;i++)
			if(a[i]<2)
				k++;
		printf("%d\n",k);
	}
}