j536 - 不穩定的礦石 (Ore)
題目描述
題目描述了有 n 個礦石，每個礦石都有一個數值。有一個不穩定的礦石，其數值會吸收左右相鄰的礦石數值。題目要求計算不穩定礦石最終的數值以及剩餘礦石的總數。不穩定礦石的位置由輸入決定，吸收範圍由 a 決定。
解題思路
這題的解題思路是先找到數值最大的礦石，這個礦石就是不穩定的礦石。然後，根據給定的 a 值，將不穩定礦石左右 a 個礦石的數值加到不穩定礦石上，並將這些礦石的數值設為 0。最後，計算不穩定礦石的數值以及剩餘礦石的總數。需要注意邊界情況，例如當 a 大於礦石陣列的長度時，或者不穩定礦石的位置靠近陣列的邊緣時。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int n,a,arr[505],ma,mit,sum;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> a;
a/=2;
for(int i=0;i<n;++i){
cin >> arr[i];
if(arr[i]>ma){
ma=arr[i];
mit=i;
}
}
for(int i=max(0,mit-a-max(0,-(n-mit-1-a)));i<mit;++i){
arr[mit]+=arr[i];
arr[i]=0;
}
for(int i=mit+1;i<=min(n-1,mit+a+max(0,-(mit-a)));++i){
arr[mit]+=arr[i];
arr[i]=0;
}
for(int i=0;i<n;++i){
if(i!=mit){
sum+=arr[i];
}
}
cout << arr[mit] << " " << sum;
}