d925 - 平均高度
題目描述
題目描述一個 M x N 的方格地圖，初始高度為 0。大力士會進行 T 次鎚擊，每次鎚擊位置為 (x, y)，力量為 k。鎚擊會使 (x, y) 的高度降低 k，周圍八個格子（包括自身）的高度增加 k。要求計算鎚擊完成後的地圖平均高度，並精確到小數點後兩位。
解題思路
這題的核心在於模擬鎚擊的影響，並計算最終的平均高度。由於地圖的尺寸可能很大，直接模擬每個格子的高度變化會導致時間超限。因此，可以採用以下策略：
- 邊界處理： 對於位於邊緣或角落的格子，其周圍的格子數量會減少，需要特殊處理。
- 影響範圍： 每次鎚擊時，計算受影響的格子數量和總高度變化。
- 平均高度計算： 最後，將總高度變化除以 M * N 即可得到平均高度。
程式碼中，根據 (x, y) 的位置，計算了不同情況下周圍格子的數量，並相應地調整了高度變化。例如，如果 (x, y) 位於角落，則周圍有 3 個格子會受到影響；如果位於邊緣，則周圍有 5 或 7 個格子會受到影響；如果位於內部，則周圍有 8 個格子會受到影響。
複雜度分析
- 時間複雜度: O(T)
- 空間複雜度: O(1)
程式碼
#include <iostream>
#include <iomanip>
using namespace std;
int main(int argc, char** argv) {
ios::sync_with_stdio(0);
cin.tie(0);
int m,n,t,x,y,k;
cin>>m>>n>>t;
double ans=0;
if(m>1&&n>1){
while(t--){
cin>>x>>y>>k;
if((x==1&&y==1)||(x==1&&y==n)||(x==m&&y==1)||(x==m&&y==n))
ans+=k<<1;
else if(x==1||x==m||y==1||y==n)
ans+=k<<2;
else
ans+=k*7;
}
}
else{
if(n!=1)
while(t--){
cin>>x>>y>>k;
if(y!=1&&y!=n)
ans+=k;
}
else if(m!=1)
while(t--){
cin>>x>>y>>k;
if(x!=1&&x!=m)
ans+=k;
}
else
while(t--){
cin>>x>>y>>k;
ans-=k;
}
}
cout<<fixed<<setprecision(2)<<ans/(m*n)<<"\n";
return 0;
}