太原网站建设小程序,互联网公司取名,wordpress字体目录,建e网室内设计网的简介5407. 管道 - AcWing题库 有一根长度为 len的横向的管道#xff0c;该管道按照单位长度分为 len 段#xff0c;每一段的中央有一个可开关的阀门和一个检测水流的传感器。 一开始管道是空的#xff0c;位于 Li 的阀门会在 Si 时刻打开#xff0c;并不断让水流入管道。…5407. 管道 - AcWing题库 有一根长度为 len的横向的管道该管道按照单位长度分为 len 段每一段的中央有一个可开关的阀门和一个检测水流的传感器。 一开始管道是空的位于 Li 的阀门会在 Si 时刻打开并不断让水流入管道。 对于位于 Li的阀门它流入的水在 TiTi≥Si时刻会使得从第 Li−(Ti−Si) 段到第 Li(Ti−Si) 段的传感器检测到水流。 求管道中每一段中间的传感器都检测到有水流的最早时间。 输入格式 输入的第一行包含两个整数 n,len用一个空格分隔分别表示会打开的阀门数和管道长度。 接下来 n 行每行包含两个整数 Li,Si用一个空格分隔表示位于第 Li 段管道中央的阀门会在 Si 时刻打开。 输出格式 输出一行包含一个整数表示答案。 数据范围 对于 30%30% 的评测用例n≤200Si,len≤3000 对于 70%70% 的评测用例n≤5000Si,len≤105 对于所有评测用例1≤n≤1051≤Si,len≤109 输入样例 3 10
1 1
6 5
10 2输出样例 5 我个人认为非常经典的二分区间合并题目一定要好好理解这道题。 根据题目水流会慢慢向两边增加求满足题目要求的时刻 t 就容易发现 t 具有单调性因为 t 越大水流流通的范围就越大就可以通过二分找到临界点 t 每次二次 t 的时候相当于 t 确定然后遍历阀门可以判断 t 时刻此阀门是否开启未开启则跳过否则把该阀门水流的范围 left 和 right 记录下来然后就是典型的区间合并问题判断是否覆盖1-len的区间。
根据题目二分过程中可能会爆int 需要开 long long 且二分范围左端点显然是1右端点需要2*len也就是2e9因为存在len为1e9时最后时刻才打开最左边或最右边阀门的最坏情况 AC code #include bits/stdc.h
using namespace std;
struct s {int l, s;
} arr[100010];int n, len;
int check(int mid) {int cnt 0;pairint, int q[100010];for (int i 1; i n; i) {if (arr[i].s mid) continue;int t mid - arr[i].s;int l max(1, arr[i].l - t), r min((long long)len, (long long) arr[i].l t);q[cnt] {l, r};}sort(q, q cnt);
// int be -1, en -1;
// for (int i 0; i cnt; i) {
// if (q[i].first en 1) {
// en max(en, q[i].second);
// } else {
// be q[i].first, en q[i].second;
// }
// }
// return be1enlen;
// if(q[0].first0) return 0;
// if(q[cnt-1].secondlen) return 0;int en q[0].second;if(q[0].first!1) return 0;for (int i 1; i cnt; i) {if (q[i].first en 1) {return 0;} enmax(en,q[i].second);}return enlen;
}
int main() {cin n len;for (int i 1; i n; i) {cin arr[i].l arr[i].s;}int l 0, r 2e9 10;while (l r) {int mid (long long)l r 1 ;if (check(mid)) r mid;else l mid 1;}cout l endl;return 0;
}
