题解 CF1469C 【Building a Fence】
Mars_Dingdang
2021-01-12 16:14:02
为了保住岌岌可危的社区贡献分,来水一篇题解(顺便抢到了截止至 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$。(高度为整数)
求是否有覆盖方式满足上述所有要求。
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1469C/639e8b11cbea2061b5e63469ccc4551e6fb009c3.png)
## 二、大体思路
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;//完美
}
```