---
title: "农田灌溉"
created: 2025-11-28
tags:
  - 算法
---

# 农田灌溉

## 题目 [农田灌溉](https://www.acwing.com/problem/content/description/4380/)

![[image-b1a5605e.png]]

## 思路分析

二分去找答案

假设x秒刚好完成所有农田的灌溉 那大于x秒就都可以把农田灌溉完成 小于这个x就不能

所以应该是个最小答案 区间划分成左半边不满足 右半边满足

即r=mid l=mid+1

主要是如何判断在经过mid秒后 农田是否全部灌溉

那就用mid去代入

同时洒水即遍历k个有洒水器的农田

因为每经过一秒向左右拓展一个农田 其实第一秒只会灌溉当前农田 不会拓展

也就是说 mid秒的话 只会向左向右拓展mid-1块农田

那假设有洒水器的农田为p[i]

则这个洒水器在mid秒能灌溉的农田为p[i]-(m-1)到p[i]+(m-1)

让j去表示它 在它的范围内j++ 但是有个条件是j存在 在1~n的范围内

如果满足 就使用s[j]记录当前农田被灌溉过了

最后检查一遍 遍历s数组 看是否全被灌溉过了

如果满足 就说明当前的mid时间是可以灌溉所有农田的 在答案的右边或者刚好在答案上

## 代码实现

**二分+暴力枚举检查**

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=210;
int p[N],s[N];
int T,n,k;

bool check(int m){
    memset(s,0,sizeof s);
    for(int i=1;i<=k;i++)
        for(int j=p[i]-(m-1);j<=p[i]+(m-1);j++)
            if(j>=1 && j<=n)
                s[j]=1;

    for(int i=1;i<=n;i++)
        if(s[i]==0)
            return false;

    return true;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>k;
        for(int i=1;i<=k;i++)   cin>>p[i];
        int l=1,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid))  r=mid;
            else    l=mid+1;
        }
        cout<<r<<endl;
    }
    return 0;
}
```

**二分+区间合并（写完“管道”回过头来写）**

每一个洒水器可以覆盖一段区间 把所有的区间合并起来

如果等于整个范围 就说明成功了

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef pair<int,int> PII;
const int N=210;
int p[N];
int T,n,k;

bool check(int m){
    vector<PII> segs;
    for(int i=1;i<=k;i++){
        int left=max(1,p[i]-(m-1)),right=min(n,p[i]+(m-1));
        segs.push_back({left,right});
    }
    sort(segs.begin(),segs.end());
    if(segs.empty() || segs[0].first>1)     return false;
    int covered=segs[0].second;
    for(int i=1;i<segs.size();i++){
        if(segs[i].first>covered+1)     return false;
        covered=max(covered,segs[i].second);
    }
    return covered==n;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>k;
        for(int i=1;i<=k;i++)   cin>>p[i];

        int l=1,r=n;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid))  r=mid;
            else    l=mid+1;
        }
        cout<<r<<endl;
    }
    return 0;
}
```

## 同类题型

## 视频讲解


---
⬅️ [[2-Learning/02-算法/03-刷题理模型/二分相关模型/借教室|借教室]] 🏠 [[00-刷题理模型]] ➡️ [[分巧克力|分巧克力]]