戳我跳转题面
题意
一共有 n 个廊桥，全部分配给互相独立的两组。第一组有 $m1$ 个区间 $[l_i,r_i]$, 第二组有 $m2$ 个区间 $[a_i,b_i]$（互相独立），一旦有廊桥空着，就会将 $i$ 区间覆盖于总区间。问一共能满足多少个区间。
思路
45pts
由于两组的处理方法几乎一样，在这里只举第一组的例子。
首先最重要的是要排个序，因为“先到先得”原则，自是按照左端点排序。
然后暴力枚举分配给第一组的廊桥个数 $i$，接着就可以 $O(1)$ 求出第二组的廊桥数量 $j$。再下去就模拟一下飞机的入场，用一个优先队列来存放正在使用的廊桥数量。如果廊桥中的飞机在当前飞机 $k$ 到达之前就应该走了，那么就将这架飞机弹出队列。最后看一下当前飞机能否入场，可以的话将飞机插入队列。答案就是枚举过程中能够停靠的飞机的总数的 $max$。
View
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
struct node
{
ll arrival, departure;
} a[N], b[N];
ll n, m1, m2, ans;
bool cmp(node x, node y) {return x.arrival < y.arrival;}
int main()
{
//freopen("airport.in", "r", stdin);
//freopen("airport.out", "w", stdout);
ans = 0;
scanf("%lld%lld%lld", &n, &m1, &m2);
for (int i = 1; i <= m1; i++)
{
scanf("%lld%lld", &a[i].arrival, &a[i].departure);
}
for (int i = 1; i <= m2; i++)
{
scanf("%lld%lld", &b[i].arrival, &b[i].departure);
}
sort(a + 1, a + m1 + 1, cmp);
sort(b + 1, b + m2 + 1, cmp);
for (int i = 0; i <= n; i++)
{
priority_queue <ll, vector <ll>, greater <ll> > q, q2;
ll j, tmp;
j = n - i, tmp = 0;
for (int k = 1; k <= m1; k++)
{
while (!q.empty() && q.top() < a[k].arrival) q.pop();
if (q.size() < i) q.push(a[k].departure), tmp++;
}
for (int k = 1; k <= m2; k++)
{
while (!q2.empty() && q2.top() < b[k].arrival) q2.pop();
if (q2.size() < j) q2.push(b[k].departure), tmp++;
}
ans = max(ans, tmp);
}
printf("%lld\n", ans);
return 0;
}
100pts
也就是相比45分暴力多了那么一点点优化。
排序是必须的，所以先按左端点排序。
然后我们分析一下暴力的复杂度，排序 $O(m1logm1+m2logm2)$，枚举 $O(n^2 ·(m1+m2))$，而这个 $O(n^2)$ 才是最大的问题。
其实我们可以设置 $res_{1,i}, res_{2,i}$ 分别表示第一组、第二组给 $i$ 个廊桥的最大停靠飞机数量。
主要部分伪代码奉上:
/*枚举所有有飞机*/
{
while (/*当堆顶飞机应该走的时候/*) /*加入空的廊桥队列，并从原堆pop该飞机*/
/*如果根本就没有廊桥是空的，说明当前飞机不可能进入廊桥*/
/*取出该飞机并加入答案*/
/*加入该飞机*/
}
最后一定要先加前缀和，然后 $ans=max (res_{1,i},res_{2,n-i})$。
Talk is cheap, show me the code.
View
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
struct node
{
ll arrival, departure;
} a[N], b[N];
ll n, m1, m2, ans;
bool cmp(node x, node y) {return x.arrival < y.arrival;}
int main()
{
//freopen("airport.in", "r", stdin);
//freopen("airport.out", "w", stdout);
ans = 0;
scanf("%lld%lld%lld", &n, &m1, &m2);
for (int i = 1; i <= m1; i++)
{
scanf("%lld%lld", &a[i].arrival, &a[i].departure);
}
for (int i = 1; i <= m2; i++)
{
scanf("%lld%lld", &b[i].arrival, &b[i].departure);
}
sort(a + 1, a + m1 + 1, cmp);
sort(b + 1, b + m2 + 1, cmp);
for (int i = 0; i <= n; i++)
{
priority_queue <ll, vector <ll>, greater <ll> > q, q2;
ll j, tmp;
j = n - i, tmp = 0;
for (int k = 1; k <= m1; k++)
{
while (!q.empty() && q.top() < a[k].arrival) q.pop();
if (q.size() < i) q.push(a[k].departure), tmp++;
}
for (int k = 1; k <= m2; k++)
{
while (!q2.empty() && q2.top() < b[k].arrival) q2.pop();
if (q2.size() < j) q2.push(b[k].departure), tmp++;
}
ans = max(ans, tmp);
}
printf("%lld\n", ans);
return 0;
}
都看到这里了，点个关注再走呗 qwq
标签：arrival,飞机,int,ll,2021,m2,廊桥,CSP From： https://www.cnblogs.com/Rainbow-Prism/p/18302718