题解 CF1469C 【Building a Fence】

为了保住岌岌可危的社区贡献分，来水一篇题解（顺便抢到了截止至 2021年1月12日15点48分 的 [最优解](https://www.luogu.com.cn/record/list?pid=CF1469C&orderBy=1&status=&page=1)）。 ## 一、题目大意 （好像没有翻译） 你需要用 $n$ 块底边为 $1$，高为 $k$ 的长边相邻长方形覆盖一个区域，第 $i$ 个长方形需要满足： 1. 最低高度为 $h_i$； 2. 相邻两块长方形的边的公共部分至少长为 $1$； 3. 第一块和最后一块长方形的底边高度必须是 $h_1,\ h_n$； 4. 长方形底边可以悬空，但高度不能比 $h_i$ 高出超过 $k-1$。（高度为整数） 求是否有覆盖方式满足上述所有要求。  ## 二、大体思路 1. 可以抽象为区间覆盖问题，将长方形看作线段，每条线段的左端点 $\ge h_i$，并且不超过左端点 $k-1$，即 $l_i\in [h_i,h_i+k-1]$。 2. 此外，相邻两条线段要有公共部分，因此左端点可以比前一条线段左端点最小值小 $k-1$，或比前一条线段左端点最大值大 $k-1$，即 $l_i\in [l_{i-1_{\min}}-k+1,l_{i-1_{\max}}+k-1]$。 3. 最后 $l_i$ 取交集，$l_i\in \left[h_i,h_i+k-1\right]\cap\left[l_{i-1_{\min}}-k+1,l_{i-1_{\max}}+k-1\right]$，即 $l_i\in \left[\max(h_i,l_{i-1_{\min}}-k+1),\min(h_i+k-1,l_{i-1_{\max}}+k-1)\right]$。 4. 因此，需要记录每条线段左端点的位置区间 $[l_{i_{\min}},l_{i_{\max}}]$，用 $[L_i,R_i]$ 表示。 5. 再根据【题目大意】第三个要求，$L_1=R_1=h_1$，然后遍历 $2\sim n$，判断 $[L_i,R_i]$ 是否合法，最后再判断 $L_n=h_n$ 即可。 （集合运算好题，理清思路就能看懂了，代码不难） ## 完整代码 ```cpp #include<iostream> #include<cstdio> #include<iomanip> #include<algorithm> #include<cmath>//少用万能头可以加快速度 using namespace std; #define rep(ii,aa,bb) for(re int ii=aa;ii<=bb;ii++) #define Rep(ii,aa,bb) for(re int ii=aa;ii>=bb;ii--) typedef long long ll; typedef unsigned long long ull; const int maxn=2e5+5;//个人习惯 namespace IO_ReadWrite{ #define re register #define gg getchar() template <typename T> inline void read(T &x){ x=0;re T f=1;re char c=gg; while(c>57||c<48){if(c=='-') f=-1;c=gg;} while(c>=48&&c<=57){x=(x<<1)+(x<<3)+(c^48);c=gg;} x*=f;return; } template <typename T> inline void write(T x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar('0'+x%10); } }//卡常快读 using namespace IO_ReadWrite; ll h[maxn],T,n,k; int main(){ read(T); while(T--){ read(n);read(k); rep(i,1,n) read(h[i]);//输入 ll l,r;l=r=h[1];//见 二.5 bool flag=1; rep(i,2,n){ l=max(h[i],l-k+1); r=min(h[i]+k-1,r+k-1);//见 二.3 //计算左端点的位置区间 if(l>r || l-h[i]>=k){//不合法 puts("NO"); flag=0; break; } } if(!flag) continue; if(l==h[n]) puts("YES");//见 二.5 else puts("NO"); } return 0;//完美 } ```