ICPC-2021 甜甜圈题解

注意

该博客是为了帮助同学学习，并非为了协助同学刷题，请读者保持自觉，请勿做CV工具人。另外为了节省篇幅，代码中不再写明#include，如果遇到我没有声明的函数，那么就是某一个头文件中的函数。

题干

原题地址：ICPC-2021-J 甜甜圈 - 牛客

艾洛喜欢吃甜食，他有n个甜甜圈，现在叠成了两叠（如下图所示），第一叠有n1个，第二叠有n2个(n1 + n2 = n)，要解决的问题如下：

每个甜甜圈都有一个唯一的甜度值S_i，甜度值两两不同
每次艾洛可以把任意一叠位于顶端的一个甜甜圈移动到另一叠顶端，若该甜甜圈是当前所有甜甜圈中最甜的（甜度值最大），那么艾洛不会移动甜甜圈，而是直接吃掉

请你求出艾洛吃完所有甜甜圈的最小移动步数。

甜甜圈

输入描述

第一行，两个正整数n1, n2(1 <= n1+n2 <= 100000)，分别表示两叠甜甜圈的个数。
第二行，n1个整数，按从顶到底的顺序排列，表示第一叠甜甜圈的甜度值。
第三行，n2个整数，按从顶到底的顺序排列，表示第二叠甜甜圈的甜度值。
保证 1 <= s_i <= 6*10⁶ 且两两互不相同。

输出描述

总共一行，一个整数，表示最少步数。

示例

输入：

1
2
3

3 3
1 4 5
2 7 3

输出：

解题过程

首先，我们很容易发现，对于任意一种情况我们都有固定的解法：

将最甜的甜甜圈上方的甜甜圈全部移动至另一侧
吃掉最甜的甜甜圈
重复1直至没有甜甜圈为止

思路非常简单，最简单的方法就是使用两个堆来模拟，但是不论是数据的移动还是最甜甜甜圈的查找都是十分耗时的操作，在这道题上显然是不可行的。

问题转化

所以这道题我们必须要另辟蹊径，不过想要找到直接算出答案的方法就算可行也十分复杂。那么我们能否换一种思路，依然使用模拟的办法，但是在模拟的过程中不真的交换两个堆中的数据呢？

答案肯定是可行的，具体细节如下：

将最甜的甜甜圈上方的甜甜圈全部移动至另一侧
如果出现与上次移动重复的部分，则减去重复部分的移动
吃掉最甜的甜甜圈
把移动过去的甜甜圈再移动回来
重复1直至没有甜甜圈为止

这个方法的核心思想就是让原本在左侧的甜甜圈始终在左侧，原本在右侧的甜甜圈始终在右侧。这样子可以简化最大值的查询以及省去数据移动。

看起来好像比原来变得更加复杂了，但是这样子进行思考的话，我们可以认为每次吃掉甜甜圈的时候直接移除掉了最甜的那一个，其它的甜甜圈并没有移动。

并且观察计算过程，我们会发现：计算结果仅与指定甜甜圈上方的甜甜圈的数量有关。那么现在我们的问题就从吃甜甜圈转变成了如何维护指定甜甜圈上方有几个甜甜圈。

直接统计是不现实的，因为如果直接统计，我们每次吃掉一个甜甜圈都需要将其下方所有甜甜圈的数据减一，这也是十分耗时的。有些小伙伴可能已经看出来了，使用树状数组维护指定甜甜圈上方的甜甜圈数量即可。

如何维护数据已经清楚了，现在就剩下最后一个问题了：如何计算？

到这里，我们就要分类讨论了：

对侧

首先来说明最简单的情况：这一次要吃掉的甜甜圈和上一次吃掉的甜甜圈不在同一侧。

这时候很明显，我们没有进行任何的重复移动，所以我们只需要直接在现有基础上再进行计算即可。

同侧

接下来再处理复杂一些的情况：这一次要吃掉的甜甜圈和上一次吃掉的甜甜圈在同一侧。

这时候就有一部分甜甜圈是不应该移动回来但是我们却把它移动回来了，所以我们要把多余的那部分减去。

那么究竟多了多少呢？我们仍然需要继续分类讨论：

我们设

上一次吃掉的甜甜圈上方有preAmount个甜甜圈

这一次要吃掉的甜甜圈上方有nowAmount个甜甜圈（不包含上一次吃掉的甜甜圈）

用result表示移动次数

下侧

如果这一次要吃掉的甜甜圈在上一次吃掉的甜甜圈的下面。

很显然，上一次所有移动回来的甜甜圈都不应该移动回来，并且我们可能还需要再移动过去一部分甜甜圈。

知道这些我们不难得出下列公式：

1
2
3

result -= preAmount;    //减去重复移动的数据
result += nowAmount - preAmount;    //加上要移动过去的数据
result += nowAmount;    //还要把数据再移动回来

化简得：

result += (nowAmount - preAmount) * 2

上侧

如果这一次要吃掉得甜甜圈在上一次吃掉得甜甜圈得上面。

很显然，这一次要吃掉得甜甜圈本身以及其上面所有的甜甜圈都不应该移动回来。

我们可以得出下列公式：

1 2	`result -= nowAmount + 1; //减去重复移动的数据 result += nowAmount; //还要把数据移动回来`

化简得：

result -= 1

数据存储与查询

现在整体思路已经没问题了，最后我们要来处理代码层面的实现问题：如何存储数据？

回过头再看一下我们的思路，不难发现我们计算时需要频繁地查询最甜的甜甜圈的位置。如果我们按照题目输入顺序存储的话查询最大值就会变得很困难，所以我们肯定需要对数据进行排序。同时我们查询的时候还需要查询数据在输入数据中的位置，那么我们肯定需要存储数据在原数组中的位置。

那么我们就能使用如下代码存储数据：

struct Donut {
    
    /** 甜度 */
    int value;
    /** 在堆中的位置 */
    int index;
    
    inline bool operator<(const Donut& that) const {
        return value < that.value;
    }
    
};

到这里，所有疑云全部都解决了，剩下的就是写出AC代码了。

AC代码

constexpr int MAX_N = 100001;

/** 甜甜圈 */
struct Donut {
    
    /** 甜度 */
    int value;
    /** 在堆中的位置 */
    int index;
    
    inline bool operator<(const Donut& that) const {
        return value < that.value;
    }
    
};

/** 树状数组 */
struct TreeArray {
    
    void init(int _size) {
        size = _size;
        for (int i = 2; i <= _size; i++) add(i, 1);
    }
    
    void add(int pos, int x) {
        while (pos <= size) {
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }
    
    int query(int left, int right) {
        int res = 0;
        while (right != 0) {
            res += tree[right];
            right -= lowbit(right);
        }
        left--;
        while (left != 0) {
            res -= tree[left];
            left -= lowbit(left);
        }
        return res;
    }
    
private:
    int tree[MAX_N];
    int size;
    
    static inline int lowbit(int x) {
        return x & -x;
    }
    
};

/** 甜甜圈堆 */
struct DonutHeap {
    
    /** 输入数据 */
    void input(int size) {
        _end = size - 1;
        for (int i = 0; i != size; ++i) {
            cin >> sorted[i].value;
            sorted[i].index = i;
        }
        sort(sorted, sorted + size);
        tree.init(size);
    }
    
    /** 判断该叠甜甜圈是否为非空 */
    inline bool notEmpty() const {
        return _end != -1;
    }
    
    /** 获取该叠甜甜圈中最甜的一个甜甜圈 */
    inline const Donut& end() {
        return sorted[_end];
    }
    
    /** 弹出该叠甜甜圈中最甜的甜甜圈 */
    inline void pop() {
        --_end;
    }
    
    /** 移除指定下标的甜甜圈 */
    inline void minus(int index) {
        tree.add(index + 2, -1);
    }
    
    /** 获取指定下标的甜甜圈上面有几个甜甜圈 */
    inline int query(int index) {
        return tree.query(1, index + 1);
    }
    
private:
    Donut sorted[MAX_N];
    TreeArray tree;
    int _end;
    
};

DonutHeap leftHeap, rightHeap;

int find() {
    if (leftHeap.notEmpty()) {
        if (rightHeap.notEmpty()) {
            return leftHeap.end().value > rightHeap.end().value ? -1 : 1;
        } else return -1;
    } else return 1;
}

typedef long long LL;

LL solve() {
    int preDirect = 0;      //存储上一次吃掉的甜甜圈在哪一侧
    int preIndex = -1;      //存储上一次吃掉的甜甜圈在其中的下标
    LL result = 0;
    while (leftHeap.notEmpty() || rightHeap.notEmpty()) {
        int direct = find();
        auto& it = direct == -1 ? leftHeap : rightHeap;
        int index = it.end().index;
        if (direct == preDirect) {   //如果要吃掉的甜甜圈和上一个吃掉的甜甜圈在同一侧
            auto preAmount = it.query(preIndex);    //上一次吃掉的甜甜圈在数组中的位置
            auto nowAmount = it.query(index);             //这一次吃掉的甜甜圈在数组中的位置
            if (preIndex < index) { //如果要吃掉的甜甜圈在上一个吃掉的甜甜圈的下面
                result += (nowAmount - preAmount) << 1;
            } else {    //如果在其上面
                result -= 1;
            }
        } else {    //如果要吃掉的甜甜圈和上一个吃掉的甜甜圈不在同一侧
            result += it.query(index) << 1;
        }
        it.minus(index);
        preIndex = index;
        preDirect = direct;
        it.pop();
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    int n1, n2;
    cin >> n1 >> n2;
    leftHeap.input(n1);
    rightHeap.input(n2);
    cout << solve();
    return 0;
}