#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 100006
typedef long long LL;
typedef struct{
int l, s;
}Tube;
typedef struct{
LL l, r;
}Sec;
Tube tube[N];
int n, len;
bool cmp( Sec a, Sec b ){
return a.l < b.l;
}
bool check( LL time ){
LL p = 0, cnt = 0;
Sec sec[N];
for( int i = 1; i <= n; i ++ ){
if( time >= tube[i].s ){
cnt ++;
LL l = tube[i].l - ( time - tube[i].s );
LL r = tube[i].l + ( time - tube[i].s );
if( l <= 0 ) sec[cnt].l = 1;
else sec[cnt].l = l;
if( r >= 1e9 ) sec[cnt].r = 1e9;
else sec[cnt].r = r;
}
}
sort( sec + 1, sec + cnt, cmp );
if( sec[1].l > 1 ) return false;
else{
LL l = 1, r = 1;
for( int i = 1; i <= cnt; i ++ ){
if( sec[i].l > r + 1 ) return false;
if( sec[i].r > r ) r = sec[i].r;
p = r;
//if( time <= 100 ) cout << time << "->";
//if( time <= 100 ) cout << r << "+" << sec[i].r << " ";
}
}
//if( time <= 100 ) cout << endl;
if( p >= len ) return true;
else return false;
}
int main(){
scanf("%d %d", &n, &len );
for( int i = 1; i <= n; i ++ ) scanf("%d %d", &tube[i].l, &tube[i].s );
LL l = 1, r = 2e9;
while( l < r ){
LL mid = l + r + 1 >> 1;
if( check( mid ) ) r = mid - 1;
else l = mid;
}
cout << l + 1 << endl;
return 0;
}
错误分析:
(1)拼接出的区间右端点值应大于等于管道总长度,但我没有进行判断
(2)在time时刻,不是所有的阀门都已经打开,计算已放水的数组sec的下标与tube数组的下标一致。导致sec数组被污染。应为sec数组新建一个变量用于存储sec的小标,杜绝了sec数组被污染
(3)拼接区间时,只要区间之间没有空隙即可,不必重叠。判断时,应小于r + 1即可