f313 - 2. 人口遷移
題目描述
題目給定一個 R x C 的城市網格，每個城市都有一定的人口數。每天，每個城市會將其人口數除以 k 的整數部分，平均分配給其相鄰的城市（上下左右）。要求模擬 m 天後，城市人口數的最大值和最小值。如果某個位置沒有城市（人口數為 -1），則該位置不能作為人口遷移的起點或終點。
解題思路
這題的核心是模擬人口遷移的過程。使用一個二維陣列 a 儲存城市的人口數，另一個二維陣列 b 儲存每天的人口變化量。
每次迭代（代表一天），計算每個城市需要遷移的人口，並將其分配給相鄰的城市。
為了避免修改原始陣列 a 時出現問題，使用輔助陣列 b 記錄每天的人口變化量，然後在每次迭代結束後，將 b 的值加到 a 上。
模擬 m 天後，遍歷 a 陣列，找到人口數的最大值和最小值。
複雜度分析
- 時間複雜度: O(r * c * m)，其中 r 是列數，c 是行數，m 是天數。因為需要模擬 m 天，每天需要遍歷整個網格。
- 空間複雜度: O(r * c)，因為需要使用兩個 r x c 的陣列
a和b儲存城市的人口數和人口變化量。
程式碼
#include <iostream>
using namespace std;
int a[51][51],r,c,k,m,b[51][51];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> r >> c >> k >> m;
for(int i=0;i<r;++i)
for(int j=0;j<c;++j)
cin >> a[i][j];
while(m--){
for(int i=0;i<r;++i){
for(int j=0;j<c;++j){
if(a[i][j]==-1)
b[i][j]=-1;
else{
int ak=a[i][j]/k;
if(i+1<r&&a[i+1][j]!=-1){
b[i+1][j]+=ak;
b[i][j]-=ak;
}
if(i>0&&a[i-1][j]!=-1){
b[i-1][j]+=ak;
b[i][j]-=ak;
}
if(j+1<c&&a[i][j+1]!=-1){
b[i][j+1]+=ak;
b[i][j]-=ak;
}
if(j>0&&a[i][j-1]!=-1){
b[i][j-1]+=ak;
b[i][j]-=ak;
}
}
}
}
for(int i=0;i<r;++i){
for(int j=0;j<c;++j){
if(a[i][j]!=-1)a[i][j]+=b[i][j];
b[i][j]=0;
}
}
}
int ans1=0,ans2=100000;
for(int i=0;i<r;++i)
for(int j=0;j<c;++j)
if(a[i][j]!=-1){
ans1=max(ans1,a[i][j]);
ans2=min(ans2,a[i][j]);
}
cout << ans2 << "\n" << ans1;
}