AcWing 5407. 管道（二分+区间合并）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 5407. 管道（二分+区间合并）原题链接中等

作者：

Pedestrian , 2024-01-02 22:36:54 , 所有人可见 , 阅读 6633

59

5

2024寒假每日一题全部题解传送门>>

首先根据题意，假如说在$ t $ 时刻满足题目要求，那么比$ t $大的时刻也一定满足要求，故具有单调性，此时可以想到用二分来做。

先来分析一下二分的范围，左端点显然是1，如何确定右端点呢？那么根据题目所给数据范围，最坏情况数据如下：

1 1000000000
1000000000 1000000000

显然此时需要时刻为$ 1999999999 $才能满足题意，故右端点至少要取到$ 2000000000 $。
不过发现右端点开到$ 1000000000 $居然也过了，该去找y总加强一下数据啦hh~

对于每个二分出来的时刻，可以将每一个水阀所能检测的范围算出来（若该时刻小于水阀打开的时刻，则该水阀跳过）。此时问题就变成了对于这些所检测出来的范围是否能覆盖整个管道，显然是一个区间合并知识点。将所有区间合并之后，再看看该区间是否能覆盖$1$~$len$的位置即可。

注：此题的区间合并并不是两个区间有交集才能合并，例如[1, 2]和[3, 4]也可以进行合并成[1, 4]

C++代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
typedef pair<int, int> PII;
PII a[N];
int n, len;

bool check(LL x)
{
    vector<PII> segs;
    for(int i = 0; i < n; i ++)
    {
        int l = a[i].first, s = a[i].second;
        if(s > x) continue; // 若当前时刻小于水阀打开的时刻，则该水阀直接跳过

        // 计算每个水阀所能检测的的范围
        int left = max(1ll, l - x + s), right = min((LL)len, l + x - s);
        segs.push_back({left, right});
    }

    int cnt = segs.size();
    sort(segs.begin(), segs.end()); // 按左端点从小到大排序

    if(segs.empty()) return false;
    if(segs[0].first > 1) return false;

    int dr = segs[0].second;
    for(int i = 1; i < cnt; i ++) // 进行区间合并
    {
        if(segs[i].first > dr + 1) return false;

        dr = max(dr, segs[i].second);
    }

    return dr == len;
}

int main()
{
    scanf("%d%d", &n, &len);

    for(int i = 0; i < n; i ++) 
    {
        int l, s;
        scanf("%d%d", &l, &s);

        a[i] = {l, s};
    }

    LL l = 1, r = 2e9;
    while(l < r) // 二分寻找答案
    {
        LL mid = l + r >> 1; // 相加过程中可能会爆int，记得要开long long
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%lld", l);
    return 0;
}

33 评论

一不小心 8个月前

管道之间是独立的？？为什么不是在第i个管道前的管道都开后才开启第i个

Pedestrian 8个月前

对的，是独立的，刚开始我做这题的我也是有这个疑问，只能说题意有点模棱两可hh

没那么多因果 9个月前

区间合并那为什么要dr + 1？

Pedestrian 9个月前

一般的区间合并是有交集才能合并，而这题不同，像[1,2],[3,4]也能进行合并，所有seg[i].second=dr+1也是能进行合并的

没那么多因果 9个月前回复了 Pedestrian 的评论

谢佬

chaomianwang 8个月前回复了 Pedestrian 的评论

就找你的回答呢hh

绝世武功 7个月前

符合条件的T不是大于每一个s吗？如果s>x，那不就可以return了吗，为什么continue啊？求大佬解答orz

Tilbur 7个月前

s>x表示当前阀门开启的时间大于当前二分的时间，也就是这个管道在当前时间是不会开启的，也就不用加入区间合并了，因为他贡献的长度是0.

Tilbur 7个月前

但是下一个管道就不一定，因为目前是无序的

者. 8个月前

114514

子夜_ 8个月前

为什么我这样写有的样例过不了诶

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int,int> PII;
const int N = 1e5 + 10;
int n,cnt;
int len;
int L[N],S[N];

bool check(int t)
{
    vector<PII> q ;//存放有水的线段
    for(int i = 1;i <= n ;i ++)
    {
        if(t >= S[i])
        {
            //注意防止范围溢出
            q.push_back({max(1,L[i] - t + S[i]),min(len,L[i] + t - S[i])});
        }
    }

    //开始区间合并
    sort(q.begin(),q.end());
    int ed = 0;
    //如果第一条线段的头都不在1，直接false
    if(q.empty()) return false;
    if(q[0].first != 1) return false;
    else
    {
        for(int i = 0; i < q.size(); i ++)
        {
            if(q[i].first <= ed + 1) ed = max(ed,q[i].second);
            else return false;
        }
    }

    if(ed == len)
        return true;
}

int main()
{
    scanf("%d%d",&n,&len);
    for(int i = 1;i <= n ;i ++) scanf("%d%d",&L[i],&S[i]);

    int l = 1,r = 2e9;
    while(l < r)
    {
        int mid = l + r >> 1; // 相加过程中可能会爆int，记得要开long long
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%d",l);

    return 0;
}

Pedestrian 8个月前

你二分的时候没开long long？

juuu- 8个月前

大佬可不可以帮我看看哪里不对呜呜呜、

#include[HTML_REMOVED]
using namespace std;
struct guan{
int w;
int t;
}g[10010];
typedef pair[HTML_REMOVED]pll;
typedef long long ll;
vector[HTML_REMOVED]v;
int n,len;
bool check(ll mid){
for(int i=0;i[HTML_REMOVED]=g[i].t){
int a=max(1ll,g[i].w-(mid-g[i].t));
int b=min((ll)len,g[i].w+(mid-g[i].t));
v.push_back({a,b});
}
}
sort(v.begin(),v.end());
if(v.empty())return false;
int st=-1,ed=-1;
for(auto i:v){
if(ed==-1)st=i.first,ed=i.second;
else if(ed+1<i.first)return false;
ed=max(ed,i.second);
}
if(st==1&&ed==len)return true;
}

int main(){
cin>>n>>len;
for(int i=0;i[HTML_REMOVED]>g[i].w>>g[i].t;
}
ll l=1,r=2e9;
while(l<r){
ll mid=(l+r)/2;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}

cai_xing 8个月前

为啥相加过程会爆int，2e9不是在int数值范围内

Pedestrian 8个月前

右端点开到了$2e9$而$l$和$r$的范围都是$1$~$2e9$,那么$l$+$r$的范围就是$2$~4e9，所以过程中是可能会爆int的。

jjya 8个月前

请问为什么y总写的int mid=(LL)l+r>>1; 把>>1换成/2就不对了 😀

Pedestrian 8个月前

那你肯定写成(LL)(l+r)/2了，写成((LL)l+r)/2就没问题啦~

kkkyrie 8个月前

谁能告诉我我这个暴力check哪里写的不对
bool check(int x) {
memset(hashs, 0, sizeof hashs);
for (int i = 1; i <= n; i) {
if (x >= q[i].y) {
int k = 1;
int l = max(k, q[i].x - x + q[i].y);
int r = min(len, q[i].x + x - q[i].y);
for (int j = l; j <= r; j) {
hashs[j] = true;
}
}
}
for (int i = 1; i <= len; i++) {
if (!hashs[i]) return false;