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 }; } };