题解：P10277 [USACO24OPEN] Bessie's Interview S

· · 题解

第一个问题比较简单，只需要用优先队列模拟，里面存下当前每个农夫面试的奶牛的结束面试的时间即可，最后输出 q.top()。

重点在第二问。好像很多题解没说清楚为什么不能用并查集，这里举出一个例子：

输入：

8 3
4 4 5 1 2 3 4 1

它对应的农夫每个时刻面试的奶牛编号是这样的：

1 2 3
1 2 3
1 2 3
1 2 3
4 5 3
6 5 7
6 8 7
6 . 7
. . 7

在第 4 时刻结束后，1,2 号农夫可以交换，因此 Bessie 可能被第 1,2 号农夫面试。

在第 5 时刻结束后，第 1,3 号农夫可以交换（如果先前 1,2 号农夫已经交换则此时 2,3 号农夫可以交换），但是交不交换无所谓，因为 Bessie 已经不可能被这两个农夫中的任何一个面试了。

而如果使用并查集，在第 5 时刻结束后，会将 1,3 号农夫合并，而先前已经将 1,2 号农夫合并。因此，如果使用并查集，最终的答案会认为 3 号农夫也是有可能面试到 Bessie 的，然而实际上不行，只不过是 1,3 号农夫最终面试的奶牛编号可能不同罢了。

那么正确的解法应该是什么呢？

拿优先队列跑过一遍后，我们可以在中途存下每个奶牛开始面试和结束面试的时间。这个值是确定的，即使面试这些奶牛的农夫可能不确定。首先拿 Bessie 开始面试的时间找到结束面试的时间为这个值的奶牛，这些奶牛是有可能在此时让 Bessie 排到后面的。继续拿这些奶牛的开始时间找结束时间相同的奶牛，最终直到找到了编号在 1 到 k 之间的奶牛，那么 Bessie 有可能排在这些奶牛的后面，而面试这些奶牛的农夫编号就是这些奶牛的编号，存下这些编号即可。

具体实现时，注意到拿第 i 号奶牛的开始时间找结束时间相同的奶牛时，不可能找到编号比 i 大的奶牛，所以可以之间从 n 到 1 倒着跑一遍，拿一个 set 维护当前需要找结束时间为多少的奶牛。遍历到一个奶牛时，如果这个奶牛的结束时间正好是我们要找的，那么就把它的开始时间放到 set 里面。如果 i\le k，那么就把一个记录最终答案的 bool 数组标记一下即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[300005],st[300005],ed[300005];
priority_queue<int,vector<int>,greater<int>>q;
set<int>s;
bool b[300005];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=k;i++){
        ed[i]=a[i];
        q.push(ed[i]);
    }
    for(int i=k+1;i<=n;i++){
        int x=q.top();q.pop();
        st[i]=x;ed[i]=x+a[i];
        q.push(ed[i]);
    }
    cout<<q.top()<<endl;
    s.insert(q.top());
    for(int i=n;i>=1;i--){
        if(s.find(ed[i])!=s.end()){
            s.insert(st[i]);
            if(i<=k)b[i]=1;
        }
    }
    for(int i=1;i<=k;i++)cout<<b[i];
    return 0;
}