ABC34C 飞行计划
大约 2 分钟贪心
ABC34C 飞行计划
【算法标签】 贪心
【语法标签】 :while循环、long long、for循环、cin/cout、max/min
给定一个初始高度,小鸟可以上下飞行,每个时间单位只能改变高度为 , 在给定多个时间点,和该时间小鸟高度的范围,判断该范围是否合理;
小鸟在某一个高度时,可以向下或者向上飞行,从 时刻到 时刻最多可以改变的高度为。
给定小鸟初始范围,则最低的高度为 范围最小值继续向下,最高高度为范围最大值继续向上。
如果这个范围与给定的范围有交集,则说明可以通过某种组合使得从时刻 到 时刻 之间的高度变化合理的存在与交集中,交集为空,则不存在这种可能性。
二、思路
初始高度为 , 即范围为 闭区间,从 时刻开始在此范围内, 再下一个时刻时求出从上一个时刻到该时刻进行极端变化时的范围,如果该范围与给定范围有交集,则可行,否则不可行。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
int N;
long long H; // 初始高度
cin >> N >> H;
long long pre_t = 0; // 上一个时间点,初始为 0;
long long low = H, high = H; // 初始区间[H,H]
bool flag = true;//标记变量,默认区间不为空
for (int i = 0; i < N; i++){
long long t, l, u;
cin >> t >> l >> u; // t 时间点高度范围[l, u]
long long d = t - pre_t; // 时间差
// 为什么要求时间差?
// 因为每秒最多上升或下降1,时间差 * 1 就是变化的数量
// 从 上一个时间点pre_t 到 t时间点之间能够移动的范围就可以去诶定了
// 是上一个时间的高度最低点 - 时间差 d * 1,到 上一个时间的最高点 + d * 1
long long new_low = low - d;
long long new_high = high + d;
// 将这个范围与给定的目标区间范围取交集
// 下边界取最大值,上边界取最小值
low = max(new_low, l);
high = min(new_high, u);
// 因为高度必须大于 0
low = max(low, (long long)1);
// 下边界大于上边界,则边界为空,该表标记
if(low > high){
flag = false;
}
//当前时间点处理结束,更新prev_t
pre_t = t;
}
//所有的区间不为空,则存在飞行区域
if(flag == true){
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}四、复杂度分析
, 根据数据范围,实际上应该不能完全过。
