a846 - C.曹冶的成績處理系統
題目描述
題目描述了曹冶老師需要處理學生成績的系統，需要支援以下三種查詢：
- 查詢指定範圍內學生的最高分。
- 查詢指定範圍內學生的平均分。
- 查詢指定學生的成績。
解題思路
這題主要考驗基本的陣列操作和迴圈應用。程式首先讀取學生人數 n 和查詢次數 m，然後讀取每個學生的成績存入陣列 a。接著，程式迴圈 m 次，每次根據查詢類型 k 執行不同的操作：
- 如果
k為 1，則讀取範圍x和y，遍歷x到y的學生，找出最高分並輸出。 - 如果
k為 2，則讀取範圍x和y，遍歷x到y的學生，計算總分，然後除以學生數量得到平均分並輸出。 - 如果
k為 3，則讀取學生編號x，直接輸出該學生的成績。
複雜度分析
- 時間複雜度: O(T * (N + M * N))，其中 T 是測試案例數量，N 是學生人數，M 是查詢次數。最壞情況下，每次查詢都需要遍歷 N 個學生。
- 空間複雜度: O(N)，主要用於儲存學生的成績陣列。
程式碼
#include <iostream>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n,m,k,x,y;
cin >> n >> m;
int a[n];
for(int i=0;i<n;++i)
cin >> a[i];
while(m--){
cin >> k;
if(k==1){
cin >> x >> y;
int maxa=-1000;
for(int i=x;i<=y;++i)
if(a[i]>maxa)
maxa=a[i];
cout << maxa << "\n";
}
else if(k==2){
cin >> x >> y;
int p=0;
for(int i=x;i<=y;++i)
p+=a[i];
cout << p/(y-x+1) << "\n";
}
else{
cin >> x;
cout << a[x] << "\n";
}
}
}
}