e660 - 00440 - Eeny Meeny Moo

🔗 前往 ZeroJudge 原題

題目描述

題目描述了在 n 個城市中，以某種方式斷開網路連線的過程。城市從 1 到 n 排序，目標是找到最小的 m 值，使得城市 2 (Ulm) 是最後一個斷線的城市。斷線的過程是從城市 1 開始，每隔 m 個城市斷線一次，並忽略已經斷線的城市。

解題思路

這題的核心是模擬斷線的過程。對於給定的 n，我們需要遍歷可能的 m 值，並模擬斷線過程，直到找到使得 Ulm (城市 2) 是最後一個斷線的 m 值。

程式使用一個陣列 a 來表示城市之間的連結關係。a[i][0] 表示城市 i 的前一個城市，a[i][1] 表示城市 i 的下一個城市。程式模擬了斷線過程，每次斷線後更新連結關係。

外層迴圈遍歷可能的 m 值，內層迴圈模擬斷線過程。在模擬過程中，程式會不斷地跳過已經斷線的城市，直到只剩下 Ulm (城市 2) 為止。

複雜度分析

• 時間複雜度: O(n * 1000) 。外層迴圈最多執行 1000 次，內層迴圈最多執行 n 次。
• 空間複雜度: O(n) 。程式使用一個大小為 155 的陣列 a 來儲存城市之間的連結關係。

程式碼

#include <iostream>
using namespace std;
int a[155][2],n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		if(n==0)break;
		for(int i=1;i<=1000;++i){
			for(int j=0;j<n;++j){
				a[j][0]=j-1;
				a[j][1]=j+1;
			}
			a[0][0]=n-1;
			a[n-1][1]=0;
			int it=0,m=n-1;
			while(m--){
				a[a[it][0]][1]=a[it][1];
				a[a[it][1]][0]=a[it][0];
				for(int k=0;k<i;++k){
					it=a[it][1];
				}
			}
			if(it==1){
				cout << i << "\n";
				break;
			}
		}
	}
}