首页 > 代码库 > LA 4725 (二分) Airport
LA 4725 (二分) Airport
题意：
有W、E两个跑道，在每个时刻每个跑道的飞机都从0开始编号，而且每个时刻都有Wi和Ei架飞机到达这两个跑道。而且每个时刻只能选择一个跑道的一架飞机起飞。问如何选择才能使得飞机的最大编号最小。(每个时刻算编号时是在飞机起飞之前的)
思路：
又是一个最大值最小的问题，可以用二分，不过怎么二分我没有想到。
参考的别人的代码：http://blog.csdn.net/u011345136/article/details/17793415
起飞的决策是这样的：
如果一条跑道是空的，另一条跑道有飞机，那么一定是选择有飞机的那条跑道起飞。
如果两条跑道都有飞机，把能起飞的次数加一记录下来。
假设最大编号为k，如果两个跑道比k多出来的那些飞机比能起飞走的次数还多，说明最大编号就比k大了，这时就不行。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 5000 + 10; 8 const int INF = 150000; 9 int a[maxn], b[maxn], n;10 11 bool check(int k)12 {13 int A = 0, B = 0, aa, bb, sum = 0; //A B分别是两条跑道的飞机数量14 for(int i = 0; i < n; ++i)15 {16 A += a[i];17 B += b[i];18 aa = max(A - k, 0);19 bb = max(B - k, 0);20 if(aa + bb > sum) return false;21 if(A == 0 && B) --B;22 else if(B == 0 && A) --A;23 else if(A && B && A + B > sum) ++sum; //A + B <= sum说明两条跑道都没有飞机了24 }25 return true;26 }27 28 int main(void)29 {30 #ifdef LOCAL31 freopen("4725in.txt", "r", stdin);32 #endif33 34 int T;35 scanf("%d", &T);36 while(T--)37 {38 scanf("%d", &n);39 for(int i = 0; i < n; ++i)40 scanf("%d%d", &a[i], &b[i]);41 42 int l = 0, r = INF;43 44 int ans; 45 while (l <= r)46 { 47 int mid = (l + r) >> 1; 48 if (check(mid))49 { 50 ans = mid; 51 r = mid - 1; 52 } 53 else l = mid + 1; 54 } 55 printf("%d\n",ans-1); 56 57 }58 59 return 0;60 }
LA 4725 (二分) Airport
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。