UVa12468

題目

http://domen111.github.io/UVa-Easy-Viewer/?12468

有一台電視共有 $100$ 臺頻道，由 $0$~$99$，並且是環狀的，也就是說我可以從 $0$ 轉到第 $99$，反之亦同

現在要從頻道 $A$ 轉到頻道 $B$，每次只能轉一臺，正向或是逆向都可，求最少的轉移數

想法

分別算出正著轉以及逆著轉所需的移動次數，取最小值即可

當我從 $0$ 轉到 $99$

1. 正轉
   $99-0=99$
2. 逆轉
   $0-99+100=1$

因為是環，所以當我轉到變成負數，只要在加上 $100$ 就可以回到應該到的位置上了

Code

//By Koios1143
#include<iostream>
using namespace std;
int main(){
	int a,b;
	while(cin>>a>>b){
		if(a==-1 && b==-1)
			break;
		int forward = b-a;
		int reverse = a-b;
		if(forward<0)
			forward+=100;
		if(reverse<0)
			reverse+=100;
		cout<<min(forward, reverse)<<"\n";
	}
	return 0;
}

複雜度分析

每筆測資時間複雜度為 $O(1)$