廊桥分配

SafariMo · 2024-08-27 13:43:17 · 题解

首先，可以写出 f(x) 表示给国内航班分配 x 个廊桥的最大停靠数量，可以用堆按题意模拟解决，时间复杂度 \mathcal O((m_1+m_2)\log (m_1+m_2))。

然后做法就显而易见了：用三分解决问题。

但是显然这个函数不是单峰函数，因为有多个峰且可能有连续的相同的函数值。

我们考虑分段三分。

分五段即可。

总时间复杂度 \mathcal O(B(m_1+m_2)\log (m_1+m_2)n \log_{\frac{3}{2}} \frac{n}{B})，B 表示分段数。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
pair<int ,int> a[N] , b[N];
int n , m1, m2;
inline int f(int x){
    if(x < 0 || x > n) return 0;
    priority_queue<int,vector<int> , greater<int> > s;
    int cnt = m1;
    for(int i = 1; i <= m1; ++ i){
        if(s.size() && s.top() < a[i].first){
            s.pop();
            s.push(a[i].second);
        }
        else{
            if(s.size() < x) s.push(a[i].second);
            else{
                -- cnt;
            } 
        }
    }
    return cnt;
}

inline int g(int x){
    if(x < 0 || x > n) return 0;
    priority_queue<int,vector<int> , greater<int> > s;
    int cnt = m2;
    for(int i = 1; i <= m2; ++ i){
        if(s.size() < x) s.push(b[i].second);
        else{
            if(s.size() && s.top() < b[i].first){
                s.pop();
                s.push(b[i].second);
            }
            else -- cnt;
        }
    }
    return cnt;
}
int L[101] , R[101];

signed main(){
    freopen("airport.in","r",stdin);
    freopen("airport.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n >> m1 >> m2;
    for(int i = 1; i <= m1; ++ i){
        cin >> a[i].first >> a[i].second;
    }  
    for(int i = 1; i <= m2; ++ i){
        cin >> b[i].first >> b[i].second;
    }
    sort(a + 1, a + m1 + 1);
    sort(b + 1, b + m2 + 1);
    int l = 0 , r = n , ans = n + 1 , res = 0;
    while(l <= r){
        int mid = l + r >> 1;
        if(f(mid) == m1){
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    if(ans != n + 1) res = f(ans) + g(n - ans);
    l = 0 , r = n;
    int anss = -1;
    while(l <= r){
        int mid = l + r >> 1;
        if(f(mid) == 0){
            anss = mid; 
            l = mid + 1;
        }
        else r = mid - 1;
    }
    if(~anss) res = max(res , f(anss) + g(n - anss));
    if(n <= 5000){
        for(int i = 0; i <= n; ++ i){
            res = max(res , f(i) + g(n - i));
        }
        cout << res << '\n';
        return 0; 
    }
    const int T = 5; 
    L[1] = max(anss , 0) , R[T] = min(ans, n);
    L[T + 1] = max(anss , 0) , R[T + 1] = min(ans , n);
    int B = (R[T] - L[1]) / T;
    for(int i = 1; i < T; ++ i){
        R[i] = L[i] + B;
        L[i + 1] = R[i] + 1;
    }
    for(int i = 1; i <= T + 1; ++ i){
        R[i] = min(R[i] , R[T]); 
    }
    for(int i = 1; i <= T + 1; ++ i){
        while(L[i] + 2 < R[i]){
            const int lmid = L[i] + (R[i] - L[i]) / 3;
            const int rmid = R[i] - (R[i] - L[i]) / 3;
            if(f(lmid) + g(n - lmid) > f(rmid) + g(n - rmid)){
                R[i] = rmid - 1;
            }
            else L[i] = lmid + 1;
        }
    //  cout << L << ' ' << R << '\n';
        for(register int j = L[i] ;j <= R[i]; ++ j){
            res = max(res , f(j) + g(n - j));
        }
    } 
    cout << res << '\n';
    return 0;
}