CSP-S 2021 廊桥分配
2021/10/25 23:39:33
本文主要是介绍CSP-S 2021 廊桥分配,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【题意】
题目链接
【分析】
很显然,如果我们能够求出f[0...N]和g[0...N]分别表示国内/外有i个停机坪时,最多的停靠飞机数量,那么max{f[i]+g[n-i]}就是答案
现在考虑如何取求f和g
我们考虑每次贪心的把新的一架飞机停在编号尽可能小的停机坪上,这样我们从前到后走一遍,借助优先级队列即可算出f和g
看看代码就很清晰了
【代码】
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; int n,m1,m2; int f[maxn],g[maxn]; struct plane { int st,ed,id; }p1[maxn],p2[maxn]; priority_queue <int,vector<int>,greater<int> > P; struct point { int opt,id,t; bool operator < (const point & oth) const{ return t<oth.t; } }; vector <point> Q; int main() { freopen("airport.in","r",stdin); freopen("airport.out","w",stdout); scanf("%d%d%d",&n,&m1,&m2); for(int i=1;i<=m1;i++) { scanf("%d%d",&p1[i].st,&p1[i].ed); p1[i].id=0; Q.push_back((point){1,i,p1[i].st}); Q.push_back((point){0,i,p1[i].ed}); P.push(i); } sort(Q.begin(),Q.end()); for(auto tmp:Q) { if(tmp.opt==1) { int q=P.top(); P.pop(); ++f[q]; p1[tmp.id].id=q; } else P.push(p1[tmp.id].id); } Q.clear(); while(P.size()) P.pop(); for(int i=1;i<=m2;i++) { scanf("%d%d",&p2[i].st,&p2[i].ed); p2[i].id=0; Q.push_back((point){1,i,p2[i].st}); Q.push_back((point){0,i,p2[i].ed}); P.push(i); } sort(Q.begin(),Q.end()); for(auto tmp:Q) { if(tmp.opt==1) { int q=P.top(); P.pop(); ++g[q]; p2[tmp.id].id=q; } else P.push(p2[tmp.id].id); } for(int i=1;i<=n;i++) f[i]+=f[i-1],g[i]+=g[i-1]; int ans=0; for(int i=0;i<=n;i++) ans=max(ans,f[i]+g[n-i]); printf("%d\n",ans); return 0; }
这篇关于CSP-S 2021 廊桥分配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升