CF-1026-C. Racing （让无人机上升还是保持不变以通过障碍） · znzryb
## 思路讲解
### 题目总结
这是一道关于无人机通过障碍门的问题。有 N 道门，每道门都有高度范围 [l_i, r_i]。无人机初始高度为 0，每次可以选择保持高度不变或上升 1 个单位。部分门的操作已经固定（0 表示保持不变，1 表示上升），部分门的操作待定（-1 表示可以自由选择）。需要判断是否存在合法方案使无人机能通过所有门，如果存在则输出一种方案，否则输出 -1。
虽然这种题不是不可能dp，但dp不太可能。
容易想到一种贪心，在每一道门前尽量增加高度，
**但是要注意这个高度的上界是什么。**
```cpp
// 在每一道门前尽量增加高度，但是要注意这个高度的上界是什么
ROF(i,N,1){
ll r=lr[i][1];
if(D[i]==1){
// 这里-1是因为这里当然不会判断，但是当mnR[i-1]来读这个mnR[i]的时候
// 我们希望mnR[i-1]的上界不能是mnR[i]，因为+1就超了
// 连续操作与传递同理
mnR[i]=min(r-1,mnR[i+1]-1);
}else{
mnR[i]=min(r,mnR[i+1]);
}
}
```
这个上界不仅会受到后续最小 r 的影响，还会收到固定操作的影响
## AC代码
[https://codeforces.com/contest/2110/submission/323871174](https://codeforces.com/contest/2110/submission/323871174)
::: 源代码
```cpp
// Problem: C. Racing
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)
// URL: https://codeforces.com/contest/2110/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,D[MAXN];
arr2 lr[MAXN];
ll mnR[MAXN];
/*
*/
inline void init(){
FOR(i,0,N+5){mnR[i]=INF;}
}
inline void solve(){
cin>>N;
init();
FOR(i,1,N){cin>>D[i];}
FOR(i,1,N){
ll l,r;cin>>l>>r;
lr[i]={l,r};
}
// li>rj i<j 时必定无解。
ll mxl=0;
FOR(i,1,N){
ll l=lr[i][0],r=lr[i][1];
if(r<mxl){
cout<<-1<<"\n";
return;
}
mxl=max(l,mxl);
}
// 在每一道门前尽量增加高度，但是要注意这个高度的上界是什么
ROF(i,N,1){
ll r=lr[i][1];
if(D[i]==1){
mnR[i]=min(r-1,mnR[i+1]-1);
}else{
mnR[i]=min(r,mnR[i+1]);
}
}
ll cnt1=0,curh=0;
FOR(i,1,N){
ll l=lr[i][0],r=lr[i][1];
if(D[i]==0){
if(curh<l || curh>r){
cout<<-1<<"\n";
return;
}
}else if(D[i]==1){
curh+=1;
if(curh<l || curh>r){
cout<<-1<<"\n";
return;
}
}else{
if(curh+1<=mnR[i]){
curh+=1;
D[i]=1;
}else{
D[i]=0;
}
if(curh<l || curh>r){
cout<<-1<<"\n";
return;
}
}
}
FOR(i,1,N){cout<<D[i]<<" ";}
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--){
solve();
}
// solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2110/submission/323871174
*/
```
:::
## 心路历程（WA，TLE，MLE……）