小W与选座

发表于 |
字数统计: 544 | 阅读时长 ≈ 2
  • Code Level: ※
  • Thinking Level: ※※

Description

有n个旅客。每个旅客从si上车，在ti下车。保证si<ti。
现在这n个旅客按照随机的顺序分别在网上订票。现在有两种订票的方式。第一种是每个人都可以在订票的时候自己选择座位，选的座位要求在si到ti中都没人选过，第二种是系统在所有n个人订完票之后安排座位。每个人要求行程中不换座位，且每个座位在任意时刻最多只能分配给一个人。当然，高铁中的座位数必须满足在任意订票顺序的情况下，都能够满足所有人的订票需求。

现在小W想知道，对于两种方案，他分别需要至少安排多少个座位。

Solution

  • op1：求一条线段与其相交线段数量的最大值
  • op2：求一条线段与其包含线段数量的最大值

Details

前缀和要加前缀

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
const int nn=200005;
int n,a[nn],rot,las=0,ans1=0,sz=0,de[nn],ans2=0;
struct tra{
    int s,t;
    friend bool operator<(tra a,tra b){
        return a.s<b.s;
    }
}e[nn];
struct per{
    int id,d; friend bool operator<(per a,per b){
        return a.d>b.d;
    }
}; priority_queue<per>q;
void r_i(int &x){
    x=0; char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar()) x=x*10-'0'+c;
}
int main(){
    int i;
    scanf("%d",&n); for(i=1;i<=n;i++){
        r_i(e[i].s),r_i(e[i].t); las=max(las,e[i].t);
    } sort(e+1,e+1+n); q.push((per){1,e[1].t}); 
    per he;
    for(i=2;i<=n;i++){
        de[i]=de[i-1];
        while(!q.empty()){
            he=q.top(); if(he.d>e[i].s) break ;
            ans1=max(ans1,i-de[he.id]-1); de[i]++; q.pop(); 
        }
        q.push((per){i,e[i].t});
    }
    while(!q.empty()){ he=q.top(); q.pop(); ans1=max(ans1,n-de[he.id]); }
    printf("%d ",ans1);
    q.push((per){1,e[1].t}); sz=1;
    for(i=2;i<=n;i++){
        while(!q.empty()){
            he=q.top(); if(he.d>e[i].s) break ;
            q.pop(); sz--;
        }
        sz++; ans2=max(sz,ans2); q.push((per){i,e[i].t});
    }
    printf("%d ",ans2);
    return 0;
}