i069 - 岩石觀察 (Stones)
題目描述
題目給定一個包含 n 個整數的陣列，代表 n 個岩石的重量。目標是調整岩石的重量，使得所有岩石重量的平均值不變，但最大重量岩石與平均值的差值最小化。具體來說，需要找到重量最大的岩石和重量最小的岩石，然後將最大岩石重量減少的差值加到最小岩石重量上。
解題思路
解題思路是首先計算所有岩石重量的平均值。然後找到陣列中最大和最小的岩石重量及其索引。計算最大岩石重量與平均值的差值。最後，從最大岩石重量中減去這個差值，並將差值加到最小岩石重量上。輸出調整後的岩石重量陣列。這個方法利用貪心策略，直接調整最大和最小的岩石重量，以最小化最大岩石重量與平均值的差值。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int a[105],n,s,ma,mat,mi=1001,mit;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
for(int i=0;i<n;++i){
cin >> a[i];
if(a[i]>ma){
ma=a[i];
mat=i;
}
if(a[i]<mi){
mi=a[i];
mit=i;
}
s+=a[i];
}
s/=n;
//cout << s << " " << ma << " " << mat << " " << mi << " " << mit << "\n";
ma-=s;
a[mat]-=ma;
a[mit]+=ma;
for(int i=0;i<n;++i){
cout << a[i] << " ";
}
}