c083 - 00130 - Roman Roulette
題目描述
題目描述了羅馬輪盤的遊戲規則，n 個人圍成一圈，從第 i 個人開始數 k 個人，數到的那個人被殺掉，然後從被殺的人的下一個人重新開始數 k 個人，直到只剩下一個人。題目要求找到起始位置 i，使得自己（位置 1）成為最後的存活者。
解題思路
此題採用模擬的方法。對於每組輸入 n 和 k，程式會模擬整個遊戲過程，嘗試不同的起始位置 ans，直到找到一個起始位置使得位置 1 能夠存活到最後。
程式使用一個陣列 a 來表示圓圈中每個人的前後關係。a[i][0] 表示 i 的前一個人，a[i][1] 表示 i 的下一個人。
在模擬過程中，程式會不斷地數 k 個人，殺掉那個人，並更新圓圈中每個人的前後關係。
如果位置 1 能夠存活到最後，程式會輸出對應的起始位置 ans+1。
複雜度分析
- 時間複雜度: O(n^2)
- 外層迴圈遍歷所有可能的起始位置，最壞情況下需要遍歷 n 次。
- 內層迴圈模擬遊戲過程，最壞情況下需要遍歷 n 次。
- 空間複雜度: O(n)
- 程式使用一個大小為 n 的陣列
a來儲存圓圈中每個人的前後關係。
- 程式使用一個大小為 n 的陣列
程式碼
#include <iostream>
using namespace std;
int n,k,a[101][2];
int main(){
while(cin >> n >> k){
if(n==0&&k==0)break;
int ac=1;
for(int ans=0;ans<n&∾++ans){
int s=ans,t=n,d,b=1;
for(int i=0;i<n;++i){
a[i][0]=i-1;
a[i][1]=i+1;
}
a[0][0]=n-1;
a[n-1][1]=0;
while(t-->1&&b){
int tt=k;
if(t==n-1)--tt;
while(tt){
tt--;
s=a[s][1];
}
if(s==0)b=0;
d=s;
tt=k;
while(tt){
tt--;
d=a[d][1];
if(d==s){
d=a[d][1];
}
}
a[a[d][0]][1]=a[d][1];
a[a[d][1]][0]=a[d][0];
a[d][0]=a[s][0];
a[d][1]=a[s][1];
a[a[s][0]][1]=d;
a[a[s][1]][0]=d;
}
if(b){
cout << ans+1 << "\n";
break;
}
}
}
}