题解 P6099 【[USACO19FEB]Dishwashing G】

45dino · 2020-03-17 18:43:47 · 题解

这道题还是挺考验思维的，我思考了一下午才AC。

我才不会告诉你我是边水犇犇边玩candybox边玩巴克球边写英语作业边做题的，其实真正代码只写了5min。

把问题转换成人话，就是要求前ans个脏盘子必须按顺序排列,输出ans（注意是输入的前ans个而不是编号的前ans个）。

还是看不懂？手玩一下样例：

看完这排版极为凌乱的图后，有没有一种一脸懵逼茅塞顿开的感觉呢，如果有，就试着写一写吧。

附上喜闻乐见的代码：

#include<bits/stdc++.h>
using namespace std;
int n,placed,base[100001];
vector<int> item[100001];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(x<placed)
        {
            cout<<i-1;
            return 0;
        }
        for(int j=x;j>0&&!base[j];j--)
            base[j]=x;
        while(!item[base[x]].empty()&&item[base[x]].back()<x)
        {
            placed=item[base[x]].back();
            item[base[x]].pop_back();
        }
        item[base[x]].push_back(x);
    }
    cout<<n;
    return 0;
}