Official Editorial

https://scg3.piaoztsdy.cn/p/16

很明显，能移除的要立刻移除，它们会阻碍交换。
一共要移除张床，这需要点体力。
由于删除时总要保证上下铺人员类型一致，故上下铺 X 的个数要相等。设上下铺 X 的个数原来相差个，则交换一个 XZ（或 ZX）会使得某一边减少一个 X，而另一边增加一个 X，差值减少，故这需要点体力。
由样例可知，删除两个相邻的 XZ 和 ZX 需要点额外体力（删除所需的体力已经计算过了）。上一步完成后，ZX 和 XZ 一定都存在（否则两列 X 的个数不可能相同），因此总会有两行相邻的 XZ 和 ZX。设上一步结束后还剩下列，则这需要点体力。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    freopen("pairs.in", "r", stdin);
    freopen("pairs.out", "w", stdout);
    int n;
    cin >> n;
    int b = 0, c = 0;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        if (s == "XZ") b++, c++;
        if (s == "ZX") b--, c++;
    }
    int a = n + abs(b) / 2 + c / 2;
    cout << a << endl;
    return 0;
}

暂无评论