题目
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2726
题意
飞机,一个起飞的跑道,两个降落的跑道。每个时刻首先两个跑道降落一些飞机,然后再飞走一架飞机,最后所有还停留着的飞机按照0开始编号,问如何安排能使序号最小
思路
明显,使用二分法枚举答案
感想:
由于题目描述,不太能理解到底是如何起飞,降落,序号又是何时进行统计的,所以在最后的序号上是否要多取1卡了很久
代码
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
typedef pair<int, int> MyPos;
const int MAXN = ;
int a[MAXN];
int b[MAXN];
int sumA[MAXN];
int sumB[MAXN];
int limitedA[MAXN];
int limitedB[MAXN];
int limitedSum[MAXN];
int n;
bool check(int mx) {
int costA = , costB = ;
for (int i = ; i <= n; i++) {
costA = max(costA, sumA[i] - mx);
costB = max(costB, sumB[i] - mx);
if (costA > limitedA[i] || costB > limitedB[i] || costA + costB > limitedSum[i])return false;
}
return true;
}int main() {
#ifdef LOCAL_DEBUG
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
int T;
cin >> T;
for (int ti = ; ti <= T && cin >> n; ti++) {
for (int i = ; i <= n; i++) {
cin >> a[i] >> b[i];
}
//if (ti < 258)continue;
for (int i = ; i <= n; i++) {
sumA[i] = sumA[i - ] + a[i];
sumB[i] = sumB[i - ] + b[i];
bool addA = sumA[i - ] > limitedA[i - ];
bool addB = sumB[i - ] > limitedB[i - ];
limitedA[i] = limitedA[i - ] + (addA ? : );
limitedB[i] = limitedB[i - ] + (addB ? : );
limitedSum[i] = limitedSum[i - ] + ((limitedA[i] + limitedB[i] > limitedSum[i - ]) ? : );
}
int l = , r = n * ;
while (l < r) {
int mid = (l + r) >> ;
if (mid == l)break;
if (check(mid)) {
r = mid;
}
else {
l = mid;
}
}
cout<<l<<endl;
}
return ;
}