P7913 廊桥分配

2023-10-18 19:42:47 # OI # Problem #构造

CSP 2021 T1

题面

题目描述

当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。

机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。

L 市新建了一座机场，一共有 $n$ 个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。

现给定未来一段时间飞机的抵达、离开时刻，请你负责将 $n$ 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。

输入格式

输入的第一行，包含三个正整数 $n, m_1, m_2$ ，分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。

接下来 $m_1$ 行，是国内航班的信息，第 $i$ 行包含两个正整数 $a_{1, i}, b_{1, i}$ ，分别表示一架国内航班飞机的抵达、离开时刻。

接下来 $m_2$ 行，是国际航班的信息，第 $i$ 行包含两个正整数 $a_{2, i}, b_{2, i}$ ，分别表示一架国际航班飞机的抵达、离开时刻。

每行的多个整数由空格分隔。

输出格式

输出一个正整数，表示能够停靠廊桥的飞机数量的最大值。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

见附件中的 airport/airport3.in

样例输出 #3

见附件中的 airport/airport3.ans

提示

【样例解释 #1】

在图中，我们用抵达、离开时刻的数对来代表一架飞机，如 $(1, 5)$ 表示时刻 $1$ 抵达、时刻 $5$ 离开的飞机；用 $\surd$ 表示该飞机停靠在廊桥，用 $\times$ 表示该飞机停靠在远机位。

我们以表格中阴影部分的计算方式为例，说明该表的含义。在这一部分中，国际区有 $2$ 个廊桥， $4$ 架国际航班飞机依如下次序抵达：

首先 $(2, 11)$ 在时刻 $2$ 抵达，停靠在廊桥。
然后 $(4, 15)$ 在时刻 $4$ 抵达，停靠在另一个廊桥。
接着 $(7, 17)$ 在时刻 $7$ 抵达，这时前 $2$ 架飞机都还没离开、都还占用着廊桥，而国际区只有 $2$ 个廊桥，所以只能停靠远机位。
最后 $(12, 16)$ 在时刻 $12$ 抵达，这时 $(2, 11)$ 这架飞机已经离开，所以有 $1$ 个空闲的廊桥，该飞机可以停靠在廊桥。

根据表格中的计算结果，当国内区分配 $2$ 个廊桥、国际区分配 $1$ 个廊桥时，停靠廊桥的飞机数量最多，一共 $7$ 架。

【样例解释 #2】

当国内区分配 $2$ 个廊桥、国际区分配 $0$ 个廊桥时，停靠廊桥的飞机数量最多，一共 $4$ 架，即所有的国内航班飞机都能停靠在廊桥。

需要注意的是，本题中廊桥的使用遵循“先到先得”的原则，如果国际区只有 $1$ 个廊桥，那么将被飞机 $(1, 19)$ 占用，而不会被 $(3, 4)$ 、 $(5, 6)$ 、 $(7, 8)$ 、 $(9, 10)$ 这 $4$ 架飞机先后使用。

【数据范围】

对于 $20 \%$ 的数据， $n \le 100$ ， $m_1 + m_2 \le 100$ 。
对于 $40 \%$ 的数据， $n \le 5000$ ， $m_1 + m_2 \le 5000$ 。
对于 $100 \%$ 的数据， $1 \le n \le {10}^5$ ， $m_1, m_2 \ge 1$ ， $m_1 + m_2 \le {10}^5$ ，所有 $a_{1, i}, b_{1, i}, a_{2, i}, b_{2, i}$ 为数值不超过 ${10}^8$ 的互不相同的正整数，且保证对于每个 $i \in [1, m_1]$ ，都有 $a_{1, i} < b_{1, i}$ ，以及对于每个 $i \in [1, m_2]$ ，都有 $a_{2, i} < b_{2, i}$ 。

【感谢 hack 数据提供】

xingxuxin。
cyslngsul。

思路

通过观察不难得出性质：假如一架飞机可以停靠在某座廊桥上（每架飞机都按照一定顺序，不乱停），那么无论怎么分配，它会一直都在那座廊桥上停靠。

于是我们可以给廊桥编号，按照没有上限规则得到每座廊桥上有几架飞机会停在它上面，而上限就相当于只开放编号小于等于 $n$ 的廊桥，做个前缀和即可。

用堆维护这个东西，最后枚举下分配多少即可。

考时用线段树做了个区间问题，暴力拿了 $45$ 分。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
typedef pair<int, int> PII;
#define x first 
#define y second 

int sum1[N], sum2[N];

struct Cor
{
    int l, r;
    bool operator < (const Cor &t) const
    {
        return l < t.l;
    }
}a[N], b[N];

int main()
{
    int n, m1, m2;
    scanf("%d%d%d", &n, &m1, &m2);
    for(int i = 1; i <= m1; i++)
        scanf("%d%d", &a[i].l, &a[i].r);
    for(int i = 1; i <= m2; i++)
        scanf("%d%d", &b[i].l, &b[i].r);
    sort(a + 1, a + m1 + 1);
    sort(b + 1, b + m2 + 1);
    // 如果给廊桥编上号 每当一架飞机到达后 如果强制让它进入编号最小的廊桥 
    // 这样不会影响进入廊桥飞机的集合 且当廊桥总数增加后 原本在哪个廊桥的飞机 仍旧会进入原来的廊桥
    // 我们发现随着分配的廊桥数量不断增大的过程中 假如有廊桥的航班 它的廊桥编号一定是不变的 并且一定是当前空闲的最小的编号的廊桥
    // 增大分配的过程中 求一个前缀和即可
    priority_queue<PII, vector<PII>, greater<PII> > q1; // 停靠中
    priority_queue<int, vector<int>, greater<int> > q2; // 空闲廊桥
    for(int i = 1; i <= n; i++) q2.push(i);
    for(int i = 1; i <= m1; i++) // 按照进场时间从前向后枚举
    {
        while(!q1.empty() && a[i].l >= q1.top().x) // 释放空闲的廊桥
        {
            q2.push(q1.top().y);
            q1.pop();
        }
        if(q2.empty()) continue; // 没有空闲廊桥
        int now = q2.top(); // 分配当前最小的编号
        q2.pop();
        sum1[now]++;
        q1.push({a[i].r, now});
    }
    for(int i = 1; i <= n; i++) sum1[i] += sum1[i - 1];
    while(!q1.empty()) q1.pop();
    while(!q2.empty()) q2.pop();
    for(int i = 1; i <= n; i++) q2.push(i);
    for(int i = 1; i <= m2; i++)
    {
        while(!q1.empty() && b[i].l >= q1.top().x)
        {
            q2.push(q1.top().y);
            q1.pop();
        }
        if(q2.empty()) continue;
        int now = q2.top();
        q2.pop();
        sum2[now]++;
        q1.push({b[i].r, now});
    }
    for(int i = 1; i <= n; i++) sum2[i] += sum2[i - 1];
    int ans = 0;
    for(int i = 0; i <= n; i++)
        ans = max(ans, sum1[i] + sum2[n - i]);
    cout << ans << endl;
    return 0;
}

暴力

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 8;
const int MAXN = N << 1;

int sum1[N], sum2[N];
int ans;
bool vis[N];
vector<int> s1;
vector<int> s2;

struct Cor
{
    int l, r;
    bool operator < (const Cor &t) const 
    {
        return l < t.l;
    }
}a[N], b[N];
struct Node
{
    int l, r;
    int sum, tmax;
    int add;
}tr[N << 3];

int find1(int x)
{
    return lower_bound(s1.begin(), s1.end(), x) - s1.begin();
}
int find2(int x)
{
    return lower_bound(s2.begin(), s2.end(), x) - s2.begin();
}
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].tmax = max(tr[u << 1].tmax, tr[u << 1 | 1].tmax);
}
void pushdown(int u)
{
    Node &root = tr[u], &left = tr[u << 1], &righ = tr[u << 1 | 1];
    if(root.add)
    {
        left.add += root.add;
        righ.add += root.add;
        left.sum += (left.r - left.l + 1) * root.add;
        righ.sum += (righ.r - righ.l + 1) * root.add;
        left.tmax += root.add;
        righ.tmax += root.add;
        root.add = 0;
    }
}
void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    tr[u].sum = 0;
    tr[u].tmax = 0;
    tr[u].add = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int x)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].add += x;
        tr[u].tmax += x;
        tr[u].sum += (tr[u].r - tr[u].l + 1) * x;
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) modify(u << 1, l, r, x);
    if(r > mid) modify(u << 1 | 1, l, r, x);
    pushup(u);
}
int query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;
    pushdown(u);
    int res = 0;
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) res += query(u << 1, l, r);
    if(r > mid) res += query(u << 1 | 1, l, r);
    return res;
}
int query_max(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r)
        return tr[u].tmax;
    pushdown(u);
    int res = 0;
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) res = max(res, query_max(u << 1, l, r));
    if(r > mid) res = max(res, query_max(u << 1 | 1, l, r));
    return res;
}

int main()
{
    // freopen("E:\\下载\\airport\\airport\\airport3.in", "r", stdin);
    // freopen("E:\\下载\\airport\\airport\\airport3.out", "w", stdout);
    int n, m1, m2;
    scanf("%d%d%d", &n, &m1, &m2);
    if(n >= m1 + m2)
    {
        cout << m1 + m2 << endl;
        return 0;
    }
    for(int i = 1; i <= m1; i++)
    {
        scanf("%d%d", &a[i].l, &a[i].r);
        s1.push_back(a[i].l);
        s1.push_back(a[i].r);
    }
    
    for(int i = 1; i <= m2; i++)
    {
        scanf("%d%d", &b[i].l, &b[i].r);
        s2.push_back(b[i].l);
        s2.push_back(b[i].r);
    }
    
    sort(s1.begin(), s1.end());
    s1.erase(unique(s1.begin(), s1.end()), s1.end());
    sort(s2.begin(), s2.end());
    s2.erase(unique(s2.begin(), s2.end()), s2.end());
    
    sort(a + 1, a + 1 + m1);
    sort(b + 1, b + 1 + m2);
    
    // 注意数组不要越界
    for(int i = 1; i <= n; i++)
    {
        build(1, 0, m1 * 2);
        for(int j = 1; j <= m1; j++)
        {
            // if(vis[j]) continue;
            int L = find1(a[j].l);
            int R = find1(a[j].r);
            int q = query_max(1, L, R);
            if(q > i - 1) continue;
            // vis[j] = true;
            modify(1, L, R, 1);
            sum1[i]++;
        }
        // sum1[i] += sum1[i - 1];
    }
    // memset(vis, false, sizeof(vis));
    // memset(tr, 0, sizeof(tr));
    for(int i = 1; i <= n; i++)
    {
        build(1, 0, m2 * 2);
        for(int j = 1; j <= m2; j++)
        {
            // if(vis[j]) continue;
            int L = find2(b[j].l);
            int R = find2(b[j].r);
            int q = query_max(1, L, R);
            if(q > i - 1) continue;
            // vis[j] = true;
            modify(1, L, R, 1);
            sum2[i]++;
        }
        // sum2[i] += sum2[i - 1];
    }
    // for(int i = 0; i <= n; i++)
    //     cout << sum1[i] << endl;
    // for(int i = 0; i <= n; i++)
    //     cout << sum2[i] << endl;

    // for(int i = 1; i <= m1; i++)
    // {
    //     scanf("%d%d", &a[i], &b[i]);
    //     maxn = max(maxn, b[i]);
    // }
    // build(1, 1, maxn);
    // for(int i = 1; i <= m1; i++)
    //     modify(1, a[i], b[i], 1);
    // for(int i = 1; i <= m1; i++)
    // {
    //     int q = query(1, a[i]);
    //     sum1[q]++;
    // }
    // // cout << sum1[1] << endl;
    // // cout << "---" << endl;
    // for(int i = 1; i <= m1; i++)
    // {
    //     sum1[i] += sum1[i - 1];
    //     // cout << sum1[i] << endl;
    // }
    // maxn = -1;
    // for(int i = 1; i <= m2; i++)
    // {
    //     scanf("%d%d", &c[i], &d[i]);
    //     maxn = max(maxn, d[i]);
    // }
    // build(1, 1, maxn);
    // for(int i = 1; i <= m2; i++)
    //     modify(1, c[i], d[i], 1);
    // for(int i = 1; i <= m2; i++)
    // {
    //     int q = query(1, c[i]);
    //     sum2[q]++;
    // }
    // // cout << c[2] << endl;
    // // cout << "--- " << query(1, c[2]) << endl;
    // for(int i = 1; i <= m2; i++)
    // {
    //     sum2[i] += sum2[i - 1];
    //     // cout << sum2[i] << endl;
    // }
    for(int i = 0; i <= n; i++)
        ans = max(ans, sum1[i] + sum2[n - i]);
    cout << ans << endl;
    return 0;
}

2023-10-18 19:42:47 # OI # Problem #构造