c198 - 保持穩定供電
題目描述
題目描述了一個約瑟夫環的問題的變形。城市有 N 戶人，其中第 X 戶是市長。目標是找到最小的 M 值，使得在移除 N-1 戶人後，市長仍然保持供電。移除的過程是按照 M 的間隔進行的，從 1 開始數，數到 M 的人停止供電。
解題思路
這題的核心是模擬約瑟夫環的移除過程，並找到滿足條件的最小 M 值。程式碼使用暴力法，從 M = 2 開始，逐步增加 M 的值，並模擬移除 N-1 戶人的過程。在模擬過程中，使用一個陣列 a 來表示每個人的前後關係。a[i][0] 表示 i 的下一個人，a[i][1] 表示 i 的前一個人。當移除一個人時，更新其前後關係，並將指標移動到下一個人。如果模擬過程中，市長 X 能夠在移除 N-1 戶人後仍然存在，則找到滿足條件的最小 M 值。
複雜度分析
- 時間複雜度: O(N^2 * 550)。外層迴圈遍歷 M 的值，最大到 550。內層迴圈模擬移除 N-1 戶人的過程，每次移除需要 O(N) 的時間。
- 空間複雜度: O(N)。使用一個大小為 501x2 的陣列
a來儲存每個人的前後關係。
程式碼
#include <iostream>
using namespace std;
int n,x,a[501][2];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> x){
if(n==0&&x==0)break;
int ans=0;
for(int i=2;i<=550;++i){
for(int j=1;j<=n;++j){
a[j][0]=j+1;
a[j][1]=j-1;
}
a[n][0]=1;
a[1][1]=n;
int c=0,it=1,tmp=0;
while(1&&c<n){
while(tmp){
tmp--;
it=a[it][0];
}
if(it==x)break;
a[a[it][1]][0]=a[it][0];
a[a[it][0]][1]=a[it][1];
it=a[it][0];
++c;
tmp=i-1;
}
if(c==n-1){
ans=i;
break;
}
}
cout << ans << '\n';
}
}