Solution
由题目数据范围可知,最晚在$10^9$时刻打开阀门,管道最长为$10^9$,则最晚在$2*10^9$时刻流满整个管道,要在$[0,2*10^9]$时间轴内,找到第一个灌满整个管道的时刻。
可以发现,随着时间推移,我们灌水的范围只会变大不会变小,时间越多,向两边蔓延得越多,并不会减少。则一定存在某个时刻,使得这个时刻刚好会使水充满整个管道,满足这个时刻之前无法灌满整个管道,这个时刻之后都是灌满整个管道的。这样答案区间便具有了二段性,我们考虑二分。
二分
每次二分时间点,看当前时间点是否满足管道被灌满,若是,则二分左边,若不是,则二分右边
如何判断当前时间点是否满足管道被灌满
设当前二分的时间点为T
,若当前阀门的开始时刻$S_i > T$,表示当前阀门还没开始覆盖,可以忽略掉;
若$S_i <= T$ 则表示当前阀门已经开始覆盖了,且覆盖的一定是连续的一段$[L_i-(T - S_i),L_i+(T + S_i)]$
我们先把每一个阀门能覆盖的范围即区间找出来,判断最后整个管道的每一个位置是否被覆盖等价于每一个阀门能覆盖的区间是否能将整个长度为len
的管道覆盖。
因此问题转换为:给出一堆区间,问这些区间是否能将整个长度为len
的管道覆盖掉,是区间覆盖问题,也可以看成是离散的区间合并问题。一般的区间合并问题,是只能合并两个有交集或者公用一个顶点的区间,而这个题目的离散的区间合并则可以合并两个没有交集但两个线性区间之间没有其他区间的区间,即虽然两个区间的端点没有相交,也不存在交集,只要这两个区间是在线性空间上是相邻的(中间没有其他区间),就可以合并,满足条件可改为:当前区间的左端点 <= 前一个区间的右端点 + 1 即可合并
Code
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;
#define int ll
const int INF = 2e9;
typedef pair<int,int> pii;
int n,len;
std::vector<pii> a;
bool check(int mid)
{
vector<pii> b;
for (auto &x: a)
{
int L = x.first , S = x.second;
if (S <= mid)
{
int t = mid - S; //mid时刻当前阀门已经流了t时间
int l = max(1ll,L - t), r= min(len,L + t); //mid时刻当前阀门对应的区间范围
b.push_back({l,r}); //将当前区间存下来
}
}
//做区间合并
sort(b.begin(),b.end(),[](const pii &a,const pii & b) {
return a.first < b.first;
});
int st = -1, ed = -1;
for (auto &seg: b)
{
if (seg.first <= ed + 1) ed = max(ed,seg.second); //当前区间的左端点小于等于上一个区间的右端点+1,则作区间合并
else st = seg.first,ed = seg.second;
}
//cout << st << " " << ed << " " << mid << endl;
return st == 1 && ed == len; //若刚好能将整个管道覆盖,则返回true
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> len;
for (int i = 1;i <= n;i ++)
{
int l,s;
cin >> l >> s;
a.push_back({l,s});
}
int l = 0,r = INF;
//二分求最早满足覆盖整个管道的时刻
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // 在mid时刻已经覆盖整个管道,则答案一定在mid的左边(包括mid),二分左边
else l = mid + 1; //若不满足,则答案一定在mid的右边
}
cout << r << "\n";
return 0;
}
上面时间复杂度是$O(nlog(n)^2)$,因为要在check
里面做排序
突然发现不用在check
里面排序也行,只需要在外面一开始做次排序即可,
下面时间复杂度优化为O(nlogn)
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long ll;
#define int ll
const int INF = 2e9;
typedef pair<int,int> pii;
int n,len;
std::vector<pii> a;
bool check(int mid)
{
vector<pii> b;
for (auto &x: a)
{
int L = x.first , S = x.second;
if (S <= mid)
{
int t = mid - S; //mid时刻当前阀门已经流了t时间
int l = max(1ll,L - t), r= min(len,L + t); //mid时刻当前阀门对应的区间范围
b.push_back({l,r}); //将当前区间存下来
}
}
//做区间合并
// sort(b.begin(),b.end(),[](const pii &a,const pii & b) {
// return a.first < b.first;
// });
int st = -1, ed = -1;
for (auto &seg: b)
{
if (seg.first <= ed + 1) ed = max(ed,seg.second); //当前区间的左端点小于等于上一个区间的右端点+1,则作区间合并
else st = seg.first,ed = seg.second;
}
//cout << st << " " << ed << " " << mid << endl;
return st == 1 && ed == len; //若刚好能将整个管道覆盖,则返回true
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> len;
for (int i = 1;i <= n;i ++)
{
int l,s;
cin >> l >> s;
a.push_back({l,s});
}
sort(a.begin(),a.end(),[](const pii &a,const pii & b) {
return a.first + a.second< b.first + b.second;
});
int l = 0,r = INF;
//二分求最早满足覆盖整个管道的时刻
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // 在mid时刻已经覆盖整个管道,则答案一定在mid的左边(包括mid),二分左边
else l = mid + 1; //若不满足,则答案一定在mid的右边
}
cout << r << "\n";
return 0;
}