c295 - APCS-2016-1029-2最大和
題目描述
題目要求計算從每群數字中各選擇一個數字，使得總和最大，並輸出可以整除最大總和的數字。如果沒有數字可以整除最大總和，則輸出 -1。
解題思路
此題採用貪心策略。首先，對於每一群數字，選擇該群中最大的數字。將所有選出的數字加總，得到最大總和 S。然後，遍歷所有選出的數字，判斷哪些數字可以整除 S。如果存在可以整除 S 的數字，則按照它們所屬群的順序輸出這些數字。如果沒有數字可以整除 S，則輸出 -1。
複雜度分析
- 時間複雜度: O(N*M + N)，其中 N 是群數，M 是每群的數字個數。第一層迴圈遍歷所有群，第二層迴圈遍歷每群的數字，計算每群的最大值。第三層迴圈遍歷所有選出的數字，判斷是否可以整除最大總和。
- 空間複雜度: O(N)，用於儲存每群的最大值。
程式碼
#include <iostream>
using namespace std;
int main(){
int m,n;
while(cin >> m >> n){
int a[m][n],b[m]={},sum=0;
bool c=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cin >> a[i][j];
if(a[i][j]>b[i])
b[i]=a[i][j];
}
sum+=b[i];
}
cout << sum << '\n';
for(int i=0;i<m;i++){
if(sum%b[i]==0){
cout << b[i] << " ";
c=1;
}
}
if(c==0)
cout << "-1\n";
else
cout << "\n";
}
}