自动搬运

查看原文

来自洛谷，原作者为

	naturelyf > 最后在线时间：2025年7月24日8时49分 <

搬运于2025-08-24 22:55:55，当前版本为作者最后更新于2024-11-12 17:15:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题外话

和上一题一起打的模拟赛，感觉要简单一点。

题目大意

有 $n$ 辆车，给定来的顺序和走的顺序，可以将这一操作类比栈的先进后出，问最少多少个车站也就是问最少几个栈。

思路

显然贪心，具体怎么贪，需要分析。我们设 $t[i]$ 是这个车站最后进入的车的出站次序，那么后面进入的车出站次序也就是 $t[j]$ 要小于 $t[i]$ 。假设现在有一个车站，次序为 $t[1]$ ，现在来了一辆车，出站次序小于 $t[1]$ 为 $t[2]$ ，他可以选择进入这个车站或新开一个车站。如果新开一个，我们现在有两个车站且次序为 $t[1]$ 和 $t[2]$ ，如果直接加入这个车站，则可以等效得看作我们也有两个车站，只不过次序为 $+\infty$ 和 $t[2]$ ，则明显比新开一个更优，所以优先选择加入车站。

现在考虑怎么加入，可用同样的方法证明这里就不写了请自己证明一下

代码实现

首先考虑暴力，每次寻找第一个大于的车站，时间复杂度 $n^2$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
vector<int> e[N];
struct node {
    int a, b, id;
    bool friend operator<(node a, node b) { return a.a < b.a; }
} dt[N];
int main() {
    freopen("milano.in", "r", stdin);
    freopen("milano.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> dt[i].a;
        dt[i].id = i;
    }
    for (int i = 1; i <= n; i++) cin >> dt[i].b;
    sort(dt + 1, dt + n + 1);
    e[1].push_back(dt[1].b);
    int cnt = 1;
    for (int i = 2; i <= n; i++) {
        int fl = 0;
        for (int j = 1; j <= cnt; j++) {
            if (e[j].back() > dt[i].b) {
                e[j].push_back(dt[i].b);
                fl = 1;
                break;
            }//这里一直从小到大加入，所以第一个找的的就是最小的
        }
        if (!fl)
            e[++cnt].push_back(dt[i].b);
    }
    cout << cnt;
    return 0;
}

考虑优化，这个瓶颈在于找最小的大于的，要支持随机访问，我考虑过优先队列但是无法实现随机访问，所以只好使用 $set$（没错，和上一题一样用 $set$ ），代码如下：

#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
const int N=2e5+10;
int n,m;
vector<int> e[N];
struct node{
	int a,b,id;
	bool friend operator<(node a,node b){
		return a.a<b.a;
	}
}dt[N];
set<int> st;
int main(){
//	freopen("milano.in","r",stdin);
//	freopen("milano.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>dt[i].a;
		dt[i].id=i;
	}
	for(int i=1;i<=n;i++)cin>>dt[i].b;
	sort(dt+1,dt+n+1);
	st.insert(dt[1].b);
	int cnt=1;
	for(int i=2;i<=n;i++){
		auto p=st.upper_bound(dt[i].b);
		if(p==st.end())cnt++,st.insert(dt[i].b);
		else{
			st.erase(p);
			st.insert(dt[i].b);
		}
	}
	cout<<cnt;
	return 0;
}
//时间复杂度：nlogn
//优化思路：set 
//100pts