CF-1026-C. Racing （让无人机上升还是保持不变以通过障碍）

思路讲解

题目总结

这是一道关于无人机通过障碍门的问题。有 N 道门，每道门都有高度范围 [l_i, r_i]。无人机初始高度为 0，每次可以选择保持高度不变或上升 1 个单位。部分门的操作已经固定（0 表示保持不变，1 表示上升），部分门的操作待定（-1 表示可以自由选择）。需要判断是否存在合法方案使无人机能通过所有门，如果存在则输出一种方案，否则输出 -1。

虽然这种题不是不可能dp，但dp不太可能。

容易想到一种贪心，在每一道门前尽量增加高度，

但是要注意这个高度的上界是什么。

// 在每一道门前尽量增加高度，但是要注意这个高度的上界是什么
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

源代码

// 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……）