题目描述
import java.util.*;
class line{
int l;
int r;
public line(int L,int R){
l=L;
r=R;
}
}
class valve{
int L;
int S;
int myl,myr;
public valve(int l,int s){
L=l;
S=s;
}
public line get_Line(int T){
return new line(L-(T-S),L+(T-S));
}
}
public class Main{
static int n;
static int len;
static boolean check(int T,valve[] valves){
int m=0;
for(int i=0;i<n;i++){
if(valves[i].S<=T) m++;
}
line[] lines=new line[m];
int cnt=-1;
for(int i=0;i<n;i++){
if(valves[i].S<=T) lines[++cnt]=valves[i].get_Line(T);
}
Arrays.sort(lines,new Comparator<line>(){
public int compare(line a,line b){
return a.l-b.l;
};
});
int l,r=0;
int st=-1,ed=-1;
for(int i=0;i<m;i++)
{
if(lines[i].l<=ed+1) ed=ed>lines[i].r?ed:lines[i].r;
else {
st=lines[i].l;
ed=lines[i].r;
}
}
if(st<=1&&ed>=m) return true;
return false;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
len=sc.nextInt();
valve[] valves=new valve[n];
for(int i=0;i<n;i++) valves[i]=new valve(sc.nextInt(),sc.nextInt());
int l=1,r=2000000000;
while(l<r)
{
int mid=l+r>>1;
if(check(mid,valves)) r=mid;
else l=mid+1;
}
System.out.println(r);
}
}
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla