g307 - pA. 為了好吃的蘋果派(Apple Pie)
題目描述
題目要求判斷 N 個蘋果派是否通過品管測驗。對於每個蘋果派，有 K 個人進行評分。評分時，會捨棄最高分和最低分，然後計算剩餘 K-2 個分數的平均值。如果平均值大於或等於給定的閾值 T，則該蘋果派被認為是及格的。程式需要輸出所有及格蘋果派的編號，從小到大排列。如果沒有及格的蘋果派，則輸出 "A is for apple."。
解題思路
對於每個蘋果派，程式首先讀取 K 個評分，然後找出最高分和最低分。接著，計算剩餘 K-2 個分數的總和，並除以 (K-2) 得到平均值。如果平均值大於或等於 T，則輸出該蘋果派的編號。如果遍歷完所有蘋果派後，沒有找到及格的蘋果派，則輸出 "A is for apple."。
複雜度分析
- 時間複雜度: O(N * K)
- 空間複雜度: O(K)
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,k,t,ac=0,v;
cin >> n >> k >> t;
for(int i=0;i<n;++i){
int mi=1005,ma=0,s=0;
for(int j=0;j<k;++j){
cin >> v;
mi=min(v,mi);
ma=max(v,ma);
s+=v;
}
if((s-mi-ma)/(k-2)>=t){
ac=1;
cout << i << "\n";
}
}
if(ac==0){
cout << "A is for apple." << endl;
}
}