题目描述
- 在 X 轴上有 n 个不同位置的石子
- 两端的石子往中间放，放完后，位置不能是两端
- 放到石子连续为止，求最少次数与最多次数
示例
输入：[7,4,9]
输出：[1,2]
解释：
我们可以移动一次，4 -> 8，游戏结束。
或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。
输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。
题解
- 思路：需要分类讨论
- 找一段长度为 n 的路径，使得石子最多，记为 m 个
- m == n 时
- m == n-1 时
- m <= n-2 时
class Solution {
public:vector<int> numMovesStonesII(vector<int>& stones) {vector<int> res(2);int n = stones.size();sort(stones.begin(), stones.end());int m = stones.back() - stones[0] - (n - 1);res[1] = m - min(stones[1] - stones[0] - 1, stones[n - 1] - stones[n - 2] - 1);res[0] = n;for (int i = 0, j = 0; i < n; i ++ ) {while (stones[i] - stones[j] + 1 > n) j ++ ;m = i - j + 1;int r;if (m == n - 1 && stones[i] - stones[j] == i - j) r = 2;else r = n - m;res[0] = min(res[0], r);}return res;}
};
