农田灌溉
题目 农田灌溉
思路分析
二分去找答案
假设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时间是可以灌溉所有农田的 在答案的右边或者刚好在答案上
代码实现
二分+暴力枚举检查
#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;
}
二分+区间合并（写完“管道”回过头来写）
每一个洒水器可以覆盖一段区间 把所有的区间合并起来
如果等于整个范围 就说明成功了
#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;
}
💬 评论