藍橋輔導之管道

• 核心思想：二分

  • 二分時間 若t時刻成立 則之后也一定成立
  • 將mid時刻時每個閥門的水的流動區間加入對組
    • 合并區間 最終判斷是否覆蓋全管道l==1 && r == m;

•   #include <iostream>#include <cstring>#include <algorithm>#define x first#define y secondusing namespace std;typedef long long LL;typedef pair<int, int> PII;const int N = 100010;PII q[N],w[N];int n,m;bool check(int mid){int cnt=0;for(int i=0;i<n;i++){int L = w[i].x , S = w[i].y;  //取出位置和時間if(mid >= S)  //說明閥門開了{int t = mid - 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;LL l = 0,r = 2e9;while(l<r){LL mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}cout<<l;}