首页 > 代码库 > UVA1450-Airport
UVA1450-Airport
题目链接
题意:有一个飞机场,有两条待飞跑到w和e,一条起飞跑道,每一时刻只能起飞一架飞机,然后有w[i]和e[i]架飞机进入w和e跑道,飞机编号从0开始,问说如何安排起飞可以使得飞机编号的最大值最小。
思路:只要二分搜索,找到最小的答案就可以了,注意跑道上为0时,是没有飞机起飞的。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 5005; int t; int A[MAXN], B[MAXN]; int judge(int n) { int cura = 0, curb = 0, num = 0; int a, b; for (int i = 0; i < t; i++) { cura += A[i]; curb += B[i]; a = max(cura - n, 0); b = max(curb - n, 0); if (a + b > num) return false; if (cura > 0 && curb > 0 && cura + curb > num) num++; else if (cura > 0 && curb == 0) cura--; else if (cura == 0 && curb > 0) curb--; } return true; } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d", &t); for (int i = 0; i < t; i++) scanf("%d%d", &A[i], &B[i]); int L = 1, R = MAXN * 20, mid; while (L < R) { mid = (R + L) / 2; if (judge(mid)) R = mid; else L = mid + 1; } printf("%d\n", L - 1); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。