Bessie's Interview (USACO Silver 2024 Open)

例子中的schedule（Bessie）:

time       0   1   2   3   4   5   6   7   8   9
farmer 1    -----1----- -----------5-----------
farmer 2    -2- ---4--- ---------6--------- ===7===
farmer 3   -------------------3--------------------

其中farmer 1和2在时间3的时候可以自由选择5或6，但不管怎么选，7（也就是Bessie）都是在8的时间开始面试。

模拟一遍就可以容易地计算出Bessie的面试时间T（用一个数组跟踪每个farmer的面试结束时间），主要是要算出哪些farmer可能面试Bessie。

Sub Task 1提示我们考虑多个farmer在同一时间结束面试的情况，这时会出现多种方案，虽然农夫的安排可能性比较多，但我们观察到，同一个时间开始或者结束的牛的安排是固定的。通过这个关系，可以找到哪些牛在Bessie开始面试的时间正好结束，通过他们可以再找到前续的牛都有哪些，最后一直找到在时间0的时候开始面试的一组牛，这些牛对应的农夫就是我们要的可能面试Bessie的农夫。

DSU的思路是错的，见这个题解里面的例子。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, k;
int t[300005];
ll st[300005],ed[300005];
bool b[300005];
priority_queue<ll, vector<ll>, greater<ll>> q;  // 小根堆
set<ll> s;   // set of cows leading to Bessie's interview
 
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t[i]);
        ll e = 0;
        if (i >= k) {
            e = q.top(); 
            q.pop();
        }
        st[i] = e;
        ed[i] = e + t[i];
        q.push(ed[i]);
    }
    // print answer
    printf("%lld\n", q.top());
    s.insert(q.top());
    for (int i = n-1; i >= 0; i--) {
        if (s.find(ed[i]) != s.end()) {
            s.insert(st[i]);
            if (i<k) b[i]=1;
        }
    }
    for (int i = 0; i < k; i++)
        printf("%d", b[i]);
    printf("\n");
 
    return 0;
}