神人题。
首先要二分一下\(k\)。然后呢?然后就不会了。
查看题解仔细思考后,发现模拟就行了。
开一个堆,把前 \(k\) 个牛放进去。
然后对于后面的牛,你每次把堆顶的牛拿出来,然后把后面的牛放进去。由于要等到堆顶的牛跳完,所以放进去的时候要加上堆顶的牛的跳舞时间。
记录最后一头牛跳完的时间。
然后就没了。
#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
constexpr int N = 1e4 + 5;
int ans, L, R, n, tmx, d[N];
priority_queue<int, vector<int>, greater<>> q;
inline bool check(int k) {rep(i, 1, k) {q.push(d[i]);}rep(i, k + 1, n) {q.push(d[i] + q.top());q.pop();}while(!q.empty()) {ans = q.top();q.pop();}return ans <= tmx;
}
int main() {cin >> n >> tmx;rep(i, 1, n) cin >> d[i];L = 1, R = n;while(L <= R) {int mid = L + R >> 1;if(check(mid)) {R = mid - 1;}else {L = mid + 1;}}cout << L;return 0;
}