金牌厨师

题解

发布日期: 2024-03-07

金牌厨师

题意

有m位同学，每个同学有一个辣度接收范围，也就是一个区间。
然后选出部分同学，做出能让这部分同学都接受的辣度的菜。
选出的同学数为 k ，同学都能接受的辣度有 x ，也就是交集为 x 。
然后找到 $max(min(k,x))$ 。

解题思路

有一种说法，求最小的最大，铁二分题？
我的评价是，这是否有点神秘？

二分答案。

当 k 减少，区间的交集不会变少
当 x 减少，交集中区间个数不会减少

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 1e6 + 10, inf = 1 << 30;

int n, m;

vector<PII> a(N);

bool check(int x) {
    vector<int> b(N);
    for (int i = 0; i < m; i ++ ) {
        auto [l, r] = a[i];
        if (r - l + 1 >= x) {
            //也就是能接受的辣度要大于等于mid，
            //不知道为什么没有题解给出准确的说明，
            //全都在说什么区间，为什么不能根据问题实际回答呢？
            b[l + x - 1] ++ ;
            b[r + 1] -- ;
        }
    }
    for (int i = 1; i <= n; i ++ ) {
        b[i] += b[i - 1];
        if (b[i] >= x) {
            return true;
        }
    }
    return false;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) {
        int l, r;
        cin >> l >> r;
        a[i] = {l, r};
    }
    
    int l = 0, r = min(n, m), ans = 1;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
    //int t; cin >> t; while (t -- ) 
    solve();
    return 0;
}