交替放置的玻璃杯题解

题目1: 交替放置的玻璃杯

有2n个玻璃杯挨个排成一排，前n个装满苏打水，其余n个杯子为空。交换杯子的位置，使之按照满—空—满—空的模式排列，而且杯子移动的次数要最少

这道题目不在力扣里哦，提示：用分治法求解。

题目理解

我们可以发现：

1. 目标状态的下标存在规律
   • 杯满为偶数，杯空为奇数
2. 要达到目标状态，只需要交换绿色线连着的两个杯子
3. 两端的杯子必定在正确的位置，从1和$2n-2$​开始，每隔一个杯子就不在正确的位置
4. 最少的交换次数为$\lfloor n/2 \rfloor$

Method 1 双指针

使用左右指针分别从两边向中间逼近，交换杯子

伪代码

1. 初始化l=1, r=2n-2
2. 不断循环交换杯子，记录交换次数，l+=2,r+=2
3. return 交换次数

时空复杂度分析

• 时间复杂度：实际上两个指针相遇即可退出循环，循环次数为$n/2$，所以时间复杂度为$O(n)$

• 空间复杂度：只需维护一个string数组，大小为$2n$，所以空间复杂度也为$O(n)$

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 20010;
string cups[N];// full的index应该为偶数，empty的index应该为奇数
int n;
int swap_cups()
{
    int res = 0;
    int l = 1, r = 2 * n - 2;
    while (l < n && r >= n)
    {
        swap(cups[l], cups[r]);
        l += 2, r -= 2;
        res ++ ;
    }
    return res;
}
int main()
{
    int res;
    cin >> n;
    for (int i = 0; i < n; i ++ )   cups[i] = "full";
    for (int i = n; i < 2 * n; i ++ ) cups[i] = "empty";

    res = swap_cups();
    cout << res << endl;
    for (int i = 0; i < 2 * n; i ++ )
        cout << cups[i] << " ";
    return 0;
}

Method 2 分治

base case

• n = 1时自动满足满-空
• n = 2时只需交换中间两个杯子

general

$$T(n) = \begin{cases} 0 & n = 0\\ 1 & n = 1\\ T(n - 2)+1 & n \geq 2 \end{cases}$$

时空复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 20010;
string cups[N];// full的index应该为偶数，empty的index应该为奇数

int n;

int swap_cups_divide(int l, int r)
{
    if (l >= r) return 0;

    swap(cups[l], cups[r]);
    return swap_cups_divide(l + 2, r - 2) + 1;
}

int main()
{
    int res;
    cin >> n;
    for (int i = 0; i < n; i ++ )   cups[i] = "full";
    for (int i = n; i < 2 * n; i ++ ) cups[i] = "empty";

    res = swap_cups_divide(1, 2 * n - 2);
    cout << res << endl;
    for (int i = 0; i < 2 * n; i ++ )
        cout << cups[i] << " ";
    return 0;
}