Koios1143的筆記

UVa 10370

發表於 分類於

UVa 10370

題目

http://domen111.github.io/UVa-Easy-Viewer/?10370

有 $C$ 個班級，每個班級有 $N$ 個學生

給定 $N$ 個學生的成績，輸出每個班級有多少百分比的學生成績比班平均還高

想法

每個班級的成績都可以算出一個平均，算出成績後一個一個比對誰的成績比平均高，每遇到一個就紀錄下來

有了紀錄的數量以及班級學生的總數，就可以算出答案囉!

不過要特別注意兩個地方

  1. 我們的平均以及答案的比例都可能會有小數，所以要用 double 來儲存
  2. 輸出要四捨五入到小數點後第三位，記得要用 fixed 和 setprecision

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<iomanip> 
using namespace std;
int c,n,arr[1005];
int main(){
	cin>>c; 
	while(c--){
		cin>>n;
		double avg=0;
		for(int i=0 ; i<n ; i++){
			cin>>arr[i]; 
			avg+=arr[i];// 先將成績加總
		}
		avg/=n;// 再來算平均 
		int cnt=0;
		for(int i=0 ; i<n ; i++){
			if(arr[i]>avg)
				cnt++;// 記錄大於平均的數量 
		}
		cout<<fixed<<setprecision(3)<<((double)cnt/(double)n)*100.0<<"%\n";
	}
	return 0;
}

時間複雜度分析

有 $C$ 個班級，每個班級有 $N$ 筆成績要輸入，輸入的時間複雜度為 $O(CN)$

每次算出平均後，需要一個一個比對有多少大於平均的成績，時間複雜度為 $O(N)$

總時間複雜度為 $O(CN+N)$ ， 約為 $O(CN)$