Bessie's Interview

题意

有 K 名农夫同时面试奶牛，前 K 头奶牛在时刻 0 开始面试。每头奶牛 i 的面试耗时为 t[i]。

某个农夫一结束面试，就会立刻开始面试队列中的下一头奶牛。如果多个农夫同时结束，下一头奶牛可以任选其中一个空闲农夫。

在前 N 头奶牛之后，Bessie 是第 N+1 头。要求输出：

Bessie 的面试开始时间；
哪些农夫有可能面试 Bessie。

思路

先看一个小数据暴力。它在每次多个农夫同时空闲时，枚举下一批奶牛分配给这些农夫的所有可能方式，并收集 Bessie 可能遇到的农夫。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:38
 * update_at: 2026-07-11 18:42
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 15;
const int MAXK = 8;

int n, k;
ll t[MAXN];
ll bessie_time;
bool possible[MAXK];

struct State {
    ll finish_time[MAXK];
    int next_cow;
};

void dfs_state(State state);

void assign_cows_to_farmers(State state, vector<int> farmers, vector<int> cows, ll event_time, int dep, bool used[]) {
    if (dep == (int)cows.size()) {
        dfs_state(state);
        return;
    }

    int cow = cows[dep];
    for (int i = 0; i < (int)farmers.size(); i++) {
        if (!used[i]) {
            used[i] = true;
            int farmer = farmers[i];
            state.finish_time[farmer] = event_time + t[cow];
            assign_cows_to_farmers(state, farmers, cows, event_time, dep + 1, used);
            used[i] = false;
        }
    }
}

void dfs_state(State state) {
    ll min_time = state.finish_time[0];
    for (int i = 1; i < k; i++) {
        if (state.finish_time[i] < min_time) {
            min_time = state.finish_time[i];
        }
    }

    vector<int> farmers;
    for (int i = 0; i < k; i++) {
        if (state.finish_time[i] == min_time) {
            farmers.push_back(i);
        }
    }

    int remain = n - state.next_cow;
    if ((int)farmers.size() > remain) {
        bessie_time = min_time;
        for (int i = 0; i < (int)farmers.size(); i++) {
            possible[farmers[i]] = true;
        }
        return;
    }

    vector<int> cows;
    for (int i = 0; i < (int)farmers.size(); i++) {
        cows.push_back(state.next_cow + i);
    }
    state.next_cow += farmers.size();

    bool used[MAXK];
    for (int i = 0; i < MAXK; i++) {
        used[i] = false;
    }
    assign_cows_to_farmers(state, farmers, cows, min_time, 0, used);
}

void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    for (int i = 0; i < k; i++) {
        possible[i] = false;
    }

    State start;
    for (int i = 0; i < k; i++) {
        start.finish_time[i] = t[i];
    }
    start.next_cow = k;
    bessie_time = -1;

    dfs_state(start);

    cout << bessie_time << '\n';
    for (int i = 0; i < k; i++) {
        cout << (possible[i] ? '1' : '0');
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

满分做法不枚举偏好，而是记录“同时完成事件”。

用优先队列模拟面试过程。堆里保存：

text

1(当前农夫完成手上面试的时间, 农夫编号)

每次取出堆顶的最早完成时间，并把所有同一时间完成的农夫一起取出。这个集合就是一个事件。

如果这一批空闲农夫数量大于剩余未面试的普通奶牛数量，那么 Bessie 会在这个时间开始面试。

关键问题是：哪些农夫可能面试 Bessie？

假设最后我们先确定了一个可能农夫 x。如果在更早的某个事件中，x 和其他农夫同时完成，那么由于当时奶牛可以任选空闲农夫，所以这个事件里的其他农夫也可能一路交换角色，最终成为 Bessie 的面试官。

因此可以从后往前处理事件：

S 表示当前已知可能面试 Bessie 的农夫集合；
初始 S 只包含模拟时选到的那个农夫；
倒序枚举每个同时完成事件 E；
如果 S 和 E 有交集，就把整个 E 都加入 S。

这样就能得到所有可能的面试农夫。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:38
 * update_at: 2026-07-11 18:42
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 300005;

int n, k;
ll t[MAXN];
bool can_interview[MAXN];

void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }

    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    for (int i = 0; i < k; i++) {
        pq.push(make_pair(t[i], i));
    }

    int next_cow = k;
    ll bessie_time = 0;
    int first_farmer = 0;
    vector<vector<int> > events;

    while (true) {
        pair<ll, int> first = pq.top();
        pq.pop();

        vector<pair<ll, int> > event;
        event.push_back(first);

        while (!pq.empty() && pq.top().first == first.first) {
            event.push_back(pq.top());
            pq.pop();
        }

        if ((int)event.size() > 1) {
            vector<int> farmers;
            for (int i = 0; i < (int)event.size(); i++) {
                farmers.push_back(event[i].second);
            }
            events.push_back(farmers);
        }

        if (next_cow + (int)event.size() > n) {
            bessie_time = first.first;
            first_farmer = event[0].second;
            break;
        }

        for (int i = 0; i < (int)event.size(); i++) {
            int farmer = event[i].second;
            pq.push(make_pair(first.first + t[next_cow], farmer));
            next_cow++;
        }
    }

    cout << bessie_time << '\n';

    for (int i = 0; i < k; i++) {
        can_interview[i] = false;
    }
    can_interview[first_farmer] = true;

    // 从后往前传播：若某个同时完成事件里已有可能农夫，则同事件农夫都可能。
    for (int i = (int)events.size() - 1; i >= 0; i--) {
        bool has_possible = false;
        for (int j = 0; j < (int)events[i].size(); j++) {
            if (can_interview[events[i][j]]) {
                has_possible = true;
            }
        }
        if (has_possible) {
            for (int j = 0; j < (int)events[i].size(); j++) {
                can_interview[events[i][j]] = true;
            }
        }
    }

    for (int i = 0; i < k; i++) {
        cout << (can_interview[i] ? '1' : '0');
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

每头普通奶牛只会入堆一次、出堆一次。

时间复杂度为 $O(N \log K)$ ，空间复杂度为 $O(N+K)$ 。

总结

本题的重点是把“偏好不确定”转成“同时完成事件中的农夫可以互换”。

正向用优先队列确定 Bessie 的开始时间并记录事件；反向用集合传播所有可能农夫。

目录

题意

思路

代码

复杂度

总结