2520 牛的舞蹈表演 二分答案 优先队列

解决思路

 

• 二分查找：使用二分查找来确定舞台的最小大小 K。

 

• 检查函数：定义一个检查函数 check(mid)，判断在舞台大小为 mid 时，演出是否能在 T_max 时间内完成。

 

• 优先队列：使用优先队列模拟舞台上的奶牛，确保每次有奶牛完成表演时，下一头奶牛立即上台。

 

• 更新边界：根据检查函数的结果，更新二分查找的边界，直到找到最小的 K。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n, a[N], t;// 检查在舞台大小为 mid 时，演出是否能在 T_max 时间内完成
bool check(int mid) {priority_queue<int, vector<int>, greater<int>> q;for (int i = 1; i <= mid; i++) q.push(a[i]);for (int i = mid + 1; i <= n; i++) {int minn = q.top(); q.pop();q.push(minn + a[i]); // 新加入队列的 a[i] 必须是 top() 结束后加入的，而 top() 跳了 minn 时长
    }while (q.size() > 1) q.pop(); // 全部弹出，队列的最后一人就是整个队伍的跳舞时长return q.top() <= t;
}int main() {// 读取奶牛数量和演出可进行的最长时间cin >> n >> t;for (int i = 1; i <= n; i++) cin >> a[i];int L = 1, R = n, ans = n;while (L <= R) {int mid = (L + R) >> 1;if (check(mid)) {ans = mid;R = mid - 1;} else {L = mid + 1;}}cout << ans;return 0;
}