chail's Blog
博客 分类 标签
chail's Blog

目录

目录

[USACO19FEB] Dishwashing G（贪心，二分）

 收录于  类别 算法足迹
     约 1232 字   预计阅读 6 分钟 

[USACO19FEB] Dishwashing G（贪心，二分）

Bessie 和 Elsie 正在帮助 Farmer John 洗碗，这是一个比人们想象的更复杂的过程。

两头奶牛决定 Bessie 负责涂肥皂，Elsie 负责冲洗。

刚开始的时候，N 个脏盘子（保证是从 1 到 N 的一个排列）堆在 Bessie 那里，而 Elsie 这边的堆是空的。而在她们俩之间，则有一张专门放涂过肥皂的盘子的桌子。

每个冲洗步骤需要执行以下两个操作之一：

  • Bessie 从脏盘子堆顶取出一个盘子，涂上肥皂，然后放在桌子上。将这个盘子放在桌子上时，Bessie 只能放在现有的非空盘堆的顶端，或是在最右边新增一个盘堆。
  • Elsie 从桌子最左边的盘堆的顶端拿起盘子，将它冲洗后放在干净的盘堆顶端。

她们希望干净的盘堆能按编号排序，编号最小的在底端，编号最大的在顶端。然而她们发现有的时候这并不可能做到。现在给定脏盘子的堆叠顺序，请你求出一个最大前缀，使得该前缀的所有盘子洗干净后，能按上面的要求堆叠。

第一行一个整数 N（1≤N≤105）。

接下来 N 行，每行一个整数，代表 Bessie 的脏盘子堆的堆叠顺序。输入的第一个盘子在堆的顶部。

输出该序列的最大前缀长度，使得该前缀的所有盘子洗干净后，能按小号在下，大号在上的规则堆叠。

5
4
5
2
3
1
4

题意很好理解，干净盘子的序列从上到下应该是递减的，因为是叠放盘子，所以要尽可能把编号小的先洗了，让序列尽可能的长。

很容易想到的是编号小的当然要放在编号大的上面，否则无法形成合法序列。

另外每一次洗盘子只能洗最左边的堆，所以右边的堆底的盘子要比左边的堆底大，这样左边的堆洗完可以接续上右边的堆。

为了让答案有序，我们考虑当前的盘子编号 $x$，应该放在第一个堆底编号大于 $x$的堆。找第一个大于我们很熟悉，用二分就好了。

但是找到了这个堆后，我们未必能直接把 $x$ 放在堆顶，堆顶可能比 $x$ 小。这样的话只能插入了，显然只有插入才是最优的，不插入放在上面会截断已经构造好的最优解，放在最右边会打破堆底递增的有序性。插入就意味着要先把左边以及上面的合法序列弹出，弹出后我们将 $x$ 放入堆顶。

当我们遇到的 $x$ 小于我们弹出的时候不能再加入堆中了，它的加入会截断已有的合法序列，放在后面也会截断后续的构造，于是此时我们得到答案。

代码怎么写呢。从 $1$ 到 $n$ 处理盘子，当前处理的盘子是第 $i$ 个，编号为 $x$。用多个 $vector$ 模拟多个堆栈，用一个指针 $h$ 记录最右边的堆的下标，同时需用 $m$ 记录已经弹出的最大编号。

对于当前 $x$，如果它已经小于 $m$，我们处理的前 $i-1$ 个盘子已经是最优解，输出 $i-1$。否则，如果它比所有的堆底都大，那就需要再开一个堆，否则用二分找到目标堆栈压入或插入。如果插入，则需要弹出上面的盘子，记录 $m$。

#include <bits/stdc++.h>
using namespace std;
vector<int> a[100005];
int main() {
    int n;
    cin >> n;
    int h=0;
    int m=0;
    for (int i=1;i<=n;++i) {
        int x;
        cin >> x;
        if (!h) a[++h].push_back(x);
        else {
            if (x<m) {
                cout << i-1;
                return 0;
            }
            if (a[h].front()<x) {
                a[++h].push_back(x);
                continue;
            }
            int l=1,r=h;
            int s=-1;
            while (l<=r) {
                int mid=(l+r)/2;
                if (a[mid].front()>x) {
                    r=mid-1;
                    s=mid;
                }
                else l=mid+1;
            }
            while (!a[s].empty() && a[s].back()<x) {
                m = max(m,a[s].back());
                a[s].pop_back();
            }
            a[s].push_back(x);
        }
    }
    cout << n;
    return 0;
}

这道题的处理过程还是有些难想的，感觉自己的思考深度还是欠缺太多，希望通过这道题和这篇题解有所进步，继续加油！

更新于 2026-07-16
 | 主页