icpc:problems:csp_s_2021_廊桥分配
problems | |
---|---|
名称 | 廊桥分配 |
题目编号 | 2021 CSP-S T1 |
题目链接 | luogu.com.cn/… |
来源 | CCF |
算法分类 | 队列, 优先队列 |
难易程度 | 容易 |
廊桥分配
想法
贪心处理每架飞机的廊桥分配,当廊桥减少时,被分配到小编号的廊桥的飞机依旧有廊桥使用,而分配到大编号的廊桥的飞机不足廊桥使用。故仅使用优先队列分配廊桥(每当飞机到时,分配编号小的廊桥),使用优先队列维护即将分走的飞机,并及时释放廊桥。
代码实现
#include<cstdio> #include<algorithm> #include<queue> #include<vector> using namespace std; const int N = 1e5+10; struct node{ int a, b; friend bool operator<(const node x, const node y){ return x.a < y.a ; } friend bool operator>(const node x, const node y) { return x.a > y.a; } }; node line1[N], line2[N]; int n, m1, m2; int tong1[N], tong2[N]; void calc(int m, node* line, int* tong) { priority_queue<int, vector<int>, greater<int> >ports; priority_queue<node, vector<node>, greater<node> >qu; for(int i=1; i<=n; i++) ports.push(i); for(int i=1; i<=m; i++) { while((!qu.empty()) && qu.top().a < line[i].a){ ports.push(qu.top().b); qu.pop(); } if(ports.empty())continue; qu.push((node){line[i].b, ports.top()}); tong[ports.top()]++; ports.pop(); } for(int i=1; i<=n; i++) tong[i] += tong[i-1]; return ; } int main() { scanf("%d %d %d", &n, &m1, &m2); for(int i=1; i<=m1; i++) scanf("%d %d", &line1[i].a, &line1[i].b); for(int i=1; i<=m2; i++) scanf("%d %d", &line2[i].a, &line2[i].b); sort(line1+1, line1+1+m1); sort(line2+1, line2+1+m2); calc(m1, line1, tong1); calc(m2, line2, tong2); int ans = 0; for(int i=0; i<=n; i++){ ans = max(ans, tong1[i] + tong2[n-i]); } printf("%d", ans); return 0; }
/app/www/public/data/pages/icpc/problems/csp_s_2021_廊桥分配.txt · 最后更改: 2023/10/10 06:06 由 温婕莺