题解：P10225 [COCI 2023/2024 #3] Milano C.le

· · 题解

题外话

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

题目大意

有 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