璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


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 由 温婕莺