拯救牢大
656 字
3 分钟
拯救牢大
题目描述
时空发生了错乱,众多平行时空的牢大乘坐直升机从时空裂缝中出现
你作为牢大的粉丝,需要调度飞机顺利救下牢大
再一次!你能拯救他们所有吗?
N 架直升机准备降落到某个只有一条停机位的机场。其中第 i 架直升机在 T_i 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 D_i 个单位时间,即它最早可以于 T_i 时刻开始降落,最晚可以于 T_i + D_i 时刻开始降落。飞机降落并离开需要 L_i 个单位时间。
一架直升机离开时,另一架直升机可以立即在同一时刻开始降落,但是不能在前一架飞机离开前开始降落,否则牢大会坠机。
请你判断 N 架直升机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T,代表测试数据的组数。
对于每组数据,第一行包含一个整数 N。
以下 N 行,每行包含三个整数 T_i, D_i, L_i。
输出格式
对于每组数据,输出 MAN 或者 OUT,代表是否可以全部安全降落。
输入输出样例
输入 #1
230 100 1010 10 100 2 2030 10 2010 10 2020 10 20输出 #1
MANOUT说明/提示
【样例说明】
对于第一组数据,可以安排第 3 架飞机于 0 时刻开始降落,20 时刻离开。安排第 2 架飞机于 20 时刻开始降落,30 时刻离开。安排第 1 架飞机于 30 时刻开始降落,40 时刻离开。
对于第二组数据,无论如何安排,都会有飞机不能及时降落。(哦不我的牢大)
【评测用例规模与约定】
对于 30% 的数据,N <= 2。
对于 100% 的数据,1 <= T <= 10,1 <= N <= 10,0 <= T_i, D_i, L_i <= 10^5。
改编自:蓝桥杯 2023 省赛 B 组 D 题。
我的代码
#include <iostream>#include <vector>#include <algorithm>
using namespace std;
struct Plane { int t; // 到达时间 int d; // 盘旋时间 int l; // 降落耗时};
void solve() { int n; cin >> n; vector<Plane> planes(n); vector<int> p(n);
for (int i = 0; i < n; ++i) { cin >> planes[i].t >> planes[i].d >> planes[i].l; p[i] = i; // 初始化排列索引 } do { int st=0; int cur=0; int flag=1; for(int i=0;i<n;i++) { int u=p[i]; st=max(cur,planes[u].t); if(st>planes[u].d+planes[u].t) { flag=0; break; } cur=st+planes[u].l; } if(flag==1) { cout<<"MAN"<<"\n"; return; } } while (next_permutation(p.begin(), p.end())); //全排列 cout<<"OUT"<<"\n";}
int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);
int t; if (cin >> t) { while (t--) { solve(); } } return 0;}文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!




