题目描述
通过读题思考后可以知道随着时间的增多水管的水肯定是越来越多,此时发现了时间的二段性;
然后写一个check函数判断时间是否符合
循环一遍找出可以开的水管在此时间段内的范围,
使用差分在这个范围内操作但是int最多开这么大
int a[536698431];
小于1e9,此时我们使用map< i n t ,i n t >代替数组构建差分数组(map< i n t,i n t > 的作用是维护一个_“区间覆盖”_的计数),最初一点要先标记左右端点,否则会疯狂报错;
样例
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N=1e5+5;
typedef long long ll;
typedef pair<int,int>pp;
int n,s[N],p[N],len;
bool check(int mid)
{
map<int,int>q;
q[1]=0;
for(int i=0;i<n;i++)
{
if(s[i]>mid)continue;
int t=mid-s[i];
int l=max(1,p[i]-t),r=min((ll)len,(ll)p[i]+t);
q[l]++,q[r+1]--;
}
int res = 0;
for( auto qq:q)
{
res += qq.second;
if(qq.first<=len&&res== 0) return false;
}
return true;
}
int main()
{
cin>>n>>len;
for(int i=0;i<n;i++)scanf("%d%d",&p[i],&s[i]);
int l=0;ll r=2e9+1;
while(l<r)
{
ll mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla