网站公司的未来,网站建设工作领导小组,软件技术是什么专业类别,网站建设方案解救苏州久远网络CSP-S 2021 T1廊桥分配
枚举分配给国内航班和国外航班的廊桥数量#xff0c;若分配给国内机场 i i i个廊桥#xff0c;则国外机场就有 n − i n-i n−i个廊桥#xff0c;在此基础上分别判断两边各能通过多少飞机。用一个小根堆存储飞机离开的时间#xff0c;枚举到一个飞机…CSP-S 2021 T1廊桥分配
枚举分配给国内航班和国外航班的廊桥数量若分配给国内机场 i i i个廊桥则国外机场就有 n − i n-i n−i个廊桥在此基础上分别判断两边各能通过多少飞机。用一个小根堆存储飞机离开的时间枚举到一个飞机到达的时间时将小根堆中的这个到达时间之前的点弹出复杂度 O ( n ( m 1 m 2 ) ) O(n(m1m2)) O(n(m1m2))可以通过 n ≤ 5000 , m 1 m 2 ≤ 5000 n\leq5000,m_1m_2\leq5000 n≤5000,m1m2≤5000的数据拿到 40 40 40分实际 45 45 45分。
#include bits/stdc.h
#define A 100010using namespace std;
struct node {int a, b;friend bool operator (const node x, const node y) {if (x.a ! y.a) return x.a y.a;else return x.b y.b;}
}e1[A], e2[A];
int n, m1, m2, ans;int main(int argc, char const *argv[]) {cin n m1 m2;for (int i 1; i m1; i) {scanf(%d%d, e1[i].a, e1[i].b);}for (int i 1; i m2; i) {scanf(%d%d, e2[i].a, e2[i].b);}sort(e1 1, e1 m1 1);sort(e2 1, e2 m2 1);priority_queueint, vectorint, greaterint q;for (int i 0; i n; i) {int ti i, tj n - i;int sum1 0, sum2 0;if (ti 0) {sum1 0;}else {while (q.size()) q.pop();for (int j 1; j m1; j) {while (!q.empty() and e1[j].a q.top()) q.pop(), ti;if (ti - 1 0) {sum1;q.push(e1[j].b);ti--;}}}if (tj 0) {sum2 0;}else {while (q.size()) q.pop();for (int j 1; j m2; j) {while (!q.empty() and e2[j].a q.top()) q.pop(), tj;if (tj - 1 0) {sum2;q.push(e2[j].b);tj--;}}}ans max(ans, sum1 sum2);}cout ans endl;
}假设已经有 n n n架飞机通过 m m m个廊桥完成了降落如果此时来了第 n 1 n1 n1架飞机那么这架飞机不会影响之前 n n n架飞机的降落情况具体降落在哪个廊桥。所以我们可以模拟出每架飞机降落时所抵达的廊桥编号同时也就知道了每个廊桥降落过飞机的数量。 例如编号为 1 1 1的廊桥降落过 3 3 3架飞机编号为 2 2 2的廊桥降落过 3 3 3架飞机编号为 3 3 3的廊桥降落过 2 2 2架飞机在这种情况下如果有 2 2 2个廊桥那么可以停留的飞机数量就是 3 3 6 336 336如果有 3 3 3个廊桥可以停留的飞机数量就是 3 3 2 8 3328 3328。
具体实现时使用一个优先队列 q q q表示某家飞机的到达时间和离开时间与部分分做法表示的含义相同但还需要加一个所停靠廊桥的编号因此可以使用pairint,int来存储。另一个优先队列 q q qq qq表示空闲的廊桥编号初始时 n n n个廊桥都空闲所以将 n n n个廊桥都加入优先队列 q q qq qq。
#include bits/stdc.h
#define A 100010
#define pi pairint, intusing namespace std;
struct node {int a, b;friend bool operator (const node x, const node y) {if (x.a ! y.a) return x.a y.a;else return x.b y.b;}
}e1[A], e2[A];
int n, m1, m2, ans, f1[A], f2[A];int main(int argc, char const *argv[]) {cin n m1 m2;for (int i 1; i m1; i) {scanf(%d%d, e1[i].a, e1[i].b);}for (int i 1; i m2; i) {scanf(%d%d, e2[i].a, e2[i].b);}sort(e1 1, e1 m1 1);sort(e2 1, e2 m2 1);priority_queuepi, vectorpi, greaterpi q;priority_queueint, vectorint, greaterint qq;for (int i 1; i n; i) qq.push(i);for (int i 1; i m1; i) {while (!q.empty() and e1[i].a q.top().first) {qq.push(q.top().second);q.pop();}if (qq.empty()) continue;int top qq.top();qq.pop();f1[top];q.push(make_pair(e1[i].b, top));}for (int i 1; i n; i) f1[i] f1[i - 1];while (!q.empty()) q.pop();while (!qq.empty()) qq.pop();for (int i 1; i n; i) qq.push(i);for (int i 1; i m2; i) {while (!q.empty() and e2[i].a q.top().first) {qq.push(q.top().second);q.pop();}if (qq.empty()) continue;int top qq.top();qq.pop();f2[top];q.push(make_pair(e2[i].b, top));}for (int i 1; i n; i) f2[i] f2[i - 1];for (int i 0; i n; i)ans max(ans, f1[i] f2[n - i]);cout ans endl;
}
