題目大意：給出一個長度為 n 的序列 a ，現在需要構造出一個長度為 n 的序列 b ，滿足相鄰的 i 和 i + 1 下，a[ i ] 和 a[ i + 1 ] 的大小關系應該和 b[ i?] 和 b[ i + 1 ] 的大小關系相同，且相鄰的 abs( b[ i ] - b[ i + 1 ] ) <= k ，且任意的 b[ i?] 都屬于 [ L , R?] 之間
題目分析：因為最后的答案需要輸出字典序最小，所以我們可以設 [ L , R ] 為最后一個位置的可行范圍，然后倒著遞推每個位置的可行范圍，最后求出第一個位置的可行范圍就是其可行解了，在遞推可行范圍的時候，注意需要同時滿足以下三個條件：
l[ i ] >= r[ i ]
l[ i ] >= L
r[ i ] <= R
然后從第一個位置向后貪心取最小的位置就可以了
代碼： ?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int a[N],l[N],r[N];int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int n,L,R,k;scanf("%d%d%d%d",&n,&L,&R,&k);for(int i=1;i<=n;i++)scanf("%d",a+i);auto check=[&](){l[n]=L,r[n]=R;for(int i=n-1;i>=1;i--){if(a[i]==a[i+1]){l[i]=l[i+1];r[i]=r[i+1];}else if(a[i]<a[i+1]){l[i]=max(L,l[i+1]-k);r[i]=r[i+1]-1;}else if(a[i]>a[i+1]){l[i]=l[i+1]+1;r[i]=min(R,r[i+1]+k);}if(l[i]>r[i]||l[i]<L||r[i]>R)return false;}return true;};if(!check())return 0*puts("-1");int ans=l[1];for(int i=1;i<=n;i++){printf("%d ",ans);if(a[i]==a[i+1])continue;else if(a[i]>a[i+1])ans=max(ans-k,l[i+1]);else if(a[i]<a[i+1])ans=max(ans+1,l[i+1]);}puts("");return 0;
}
