Dishwashing (USACO Gold 2019 February)

Dishwashing (USACO Gold 2019 February)

此题在洛谷上难度标识很低（普及），但还是需要一定的思考的，至少应该是提高难度吧。

初步观察，Bessie能做的事情是比较有限的，可以在现有堆的顶上方盘子，或者新开堆，但是加入Elsie之后，组合就变多了，Elsie一方面可以从最左侧顶端拿盘子，改变最左侧堆的后续顺序。而如果她把最左侧堆全部拿完，则就可以把右面的堆变成最左侧的堆。这样就发现组合很多，不好想。

进一步观察之后，我们发现在这样的规则下，堆的之间有这样一些规律：

  1. 首先所谓的堆其实是个栈（stack），先进后出。
  2. 关键规律是：多个堆从左往右，底部盘子号上升，从下往上盘子号下降，只有这样才能使得最后单调上升。
  3. 所以来一个新盘子，通过底部盘子可以确定要放在哪个堆，如果比所有底部盘子大，则开新的堆。
  4. 如果发现比应该在的栈的顶部盘子号码大，那唯一的办法就是把这个stack左侧所有盘子，以及这个栈顶的盘子由Elsie洗干净（pop）掉，记录下洗干净的盘子的最大号码，然后这个盘子可以放置在这个栈（已经是新的最左的栈），并保持从下到上号码下降。
  5. 如果发现新来的盘子号码比洗干净过的盘子小，则不能再放置，过程结束。

所以总体上就是一个规则多一点的模拟过程，程序实现简单，但思维过程还是有点绕的，题目出得挺好。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;      // <= 1e5
vector<int> bottoms;
vector<stack<int>> st;
int rinsed;
int ans;
 
int main() {
    freopen("dishes.in", "r", stdin);
    freopen("dishes.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        int j = lower_bound(bottoms.begin(), bottoms.end(), a) - bottoms.begin();
        if (j == bottoms.size()) {      // new soapy stack
            bottoms.push_back(a);
            stack<int> s;
            s.push(a);
            st.push_back(s);
            ans = i+1;
            continue;
        } 
        if (a < rinsed) break;          // cannot place plate lower than last rinsed
        while (a > st[j].top()) {       // rinse plates
            rinsed = st[j].top();
            st[j].pop();
        }
        st[j].push(a);                  // place soapy plate
        ans = i+1;
    }
    printf("%d", ans);
 
    return 0;
}