【Educational Codeforces Round 101 (Rated for Div. 2) C】Building a Fence
for Codeforces div round 101 Building Educational Rated
2023-09-14 09:03:41 时间
题目链接
翻译
让你放长度为 \(k\) 的长条,相邻两列必须有一个公共位置,路不是平的,长条必须放在某个高度之上。
且最高不能高过路高上面 \(k-1\)。
规定第一列和最后一列只能老老实实放在路面上。
问你能否符合上述要求放好所有的长条。
题解
每一列处理出来一个可能的长条占据的区域 \(Occpied\) 的上下界,然后以此来决定下一列可以放长条的上下界。
根据这个上下界,和第 \(i\) 列本来就有的,能放的区域 \(h_i+1,h_i+k\) 的限制,这两个区间取交集即可,如果为空则 \(NO\)。
每一列都不为空,则 \(YES\)。
边界特殊处理一下就好。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5;
int T, n, k;
LL h[N + 10];
int main() {
#ifdef LOCAL_DEFINE
freopen("in.txt", "r", stdin);
#endif // LOCAL_DEFINE
ios::sync_with_stdio(0), cin.tie(0);
cin >> T;
while (T--) {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
bool finalOK = true;
LL minOccupied = h[1] + 1, maxOccupied = h[1] + k;
for (int i = 2; i <= n; i++) {
LL ithColumnCanPosMin, ithColumnCanPosMax;
ithColumnCanPosMin = minOccupied - k + 1, ithColumnCanPosMax = maxOccupied;
ithColumnCanPosMin = max(1LL, ithColumnCanPosMin);
LL ithColumnToPosMin = h[i] + 1, ithColumnToPosMax = h[i] + k;
if (i == n) {
ithColumnToPosMax = h[i] + 1;
}
if (ithColumnCanPosMax < ithColumnToPosMin || ithColumnToPosMax < ithColumnCanPosMin) {
finalOK = false;
}
ithColumnCanPosMin = max(ithColumnCanPosMin, ithColumnToPosMin);
ithColumnCanPosMax = min(ithColumnCanPosMax, ithColumnToPosMax);
minOccupied = ithColumnCanPosMin;
maxOccupied = ithColumnCanPosMax + k - 1;
}
if (finalOK) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
}
相关文章
- MyZip Pro for Mac(mac解压缩工具)
- Sketch for mac(专业矢量绘图设计软件)v93中文激活版
- winexec for linux[通俗易懂]
- Photoshop 2020 for Mac(PS2020)
- Lightroom Classic 2022 for Mac(Lrc2022) 11.5中文版
- Waves Complete 11 for Mac(Waves全套混音插件包) v2020.11.12 完整中文版
- Slidepad for Mac(iPad式APP切换工具)
- MacDroid for mac(安卓设备文件传输助手)
- Days for mac(菜单栏日历提醒软件)
- 苹果MacBook思维导图软件Xmind 2022 for Mac 自带激活版
- ORA-23314: database is not a materialized view site for “string”.”string” ORACLE 报错 故障修复 远程处理
- ORA-47221: Label string for Identity string.string under OLS Policy string not found ORACLE 报错 故障修复 远程处理
- ORA-54530: invalid etype for element at element offset ORACLE 报错 故障修复 远程处理
- ORA-14633: Index maintainence clause not allowed for ADD list subpartition to a Composite partitioned table ORACLE 报错 故障修复 远程处理
- ORA-14764: FOR VALUES clause cannot be specified for only one partition ORACLE 报错 故障修复 远程处理
- loopOracle中的循环编程:For Loop游标(oracle游标for)
- MySQL存储过程中使用FOR循环的实现(mysql存储过程for循环)
- Optimize Your System: Monitor Processes with htop for Linux(htoplinux)
- 解读JavaScript中For,While与递归的用法