题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int >PII;
typedef long long ll;
#define x first
#define y second
const int N=1e5+10;
int n,m;//打开的阀门 管道长度
PII w[N],q[N];//w表示初始时的第l段在s时刻打开 q表示二分之后每个阀门对应区间的左右端点
bool check(int mid)
{
int cnt=0;//打开时刻在mid及之前 的阀门的数量
for(int i=0;i<n;i++)
{
int L=w[i].x,S=w[i].y;//位置 时刻
if(S<=mid)
{
int t=mid-S;//距离s经过多长时间
int l=max(1,L-t),r=min((ll)m,(ll)L+t);
q[cnt++] ={l,r};
}
}
sort(q,q+cnt);
int st=-1,ed=-1;//起点 终点
for(int i=0;i<cnt;i++)
if(q[i].x<=ed+1) ed=max(ed,q[i].y);
else st=q[i].x,ed=q[i].y;
return st==1&&ed==m;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>w[i].x>>w[i].y;
int l=0,r=2e9;
while(l<r)
{
int mid=(ll)l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r;
return 0;
}
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla