Building a Fence
题意
用 n个宽度为1高度为k 的木板构建一段栅栏 第i个木板下面的地面高度等于 h i第一个和最后一个木板必须在地面上 其他的木板 底端 可能位于地面或者不高于地面k−1的高度上 相邻的两个木板必须有公共边 也即有重合的部分 问有没有可能建造一个符合所有规则的围栏
思路
设 l ll r rr 分别为当前栅栏下端的最小高度和最大高度 因为每段栅栏高度都为 k kk 可知 下一段栅栏底边高度的范围为[l−k+1,r+k−1] 又因为 栅栏底边最低要在地上即a[i] 最高只能达到 $a[i] + k - 1 $ 所以更新后的 lr为：
l = max(l - k + 1, a[i]); r = min(r + k - 1, a[i] + k - 1);
如果l<=r 说明可行
否则不可行
最后特判一下最后一块栅栏(只能建造在地上) 即判断一下 a[n] 是否在[l,r] 的范围内
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 200010; int n, k; int a[N]; void solve() { cin >> n >> k; for (int i = 1; i <= n; ++i)scanf("%d", &a[i]); bool flag = true; int l = a[1], r = a[1]; //栅栏修建的范围 即栅栏底边高度的范围 for (int i = 2; i <= n; ++i) { l = max(l - k + 1, a[i]); r = min(r + k - 1, a[i] + k - 1); if (l > r) { flag = false; break; //cout << "i " << i << endl; } } if (a[n] < l || a[n] > r)flag = false; if (flag)puts("YES"); else puts("NO"); } int main() { int t; cin >> t; while (t--) solve(); return 0; }
