はまやんはまやんはまやん

hamayanhamayan's blog

Moving Stones Until Consecutive [LeetCode 1033]

https://leetcode.com/contest/weekly-contest-134/problems/moving-stones-until-consecutive/

数直線の上に3つの石がある。
3つの石がa,b,cの位置にある。
以下の操作を任意回できる。
「石がx<y<zの位置にあるときに、x,zの石をxとzの間の空いている位置に移動する」
行える操作の最小回数と最大回数を答えよ。
 
1≦a,b,c≦100
a != b, b != c, c != a

解説

https://leetcode.com/submissions/detail/225423972/

最小回数は、場合分けしよう。
最小回数は0回、1回、2回のいずれかである。
0回は、全部隣接している場合
1回は、隣接しているものがあるか、1つ飛ばしになっている場合。x?yとなっていて、?にzを入れる感じ。
2回は、それ以外
 
最大回数は、[x,z]の中で空いている所の個数分だけ移動ができる。
1つずつ寄せると、最大回数が達成できる。

class Solution {
public:
	vector<int> numMovesStones(int a, int b, int c) {
		int x = min({ a,b,c });
		int z = max({ a,b,c });
		int y = a + b + c - x - z;

		int minimum_moves = -1;
		if (x + 1 == y and y + 1 == z) minimum_moves = 0;
		else if (x + 1 == y or x + 2 == y) minimum_moves = 1;
		else if (y + 1 == z or y + 2 == z) minimum_moves = 1;
		else minimum_moves = 2;

		int maximum_moves = z - x - 2;

		return { minimum_moves, maximum_moves };
	}
};