最近复习了一下堆，于是去luogu上找一些简单题写一写

 

贪心的想，小z不会到一半以后回头去Ak，因为这样从时间上想肯定是不优的，他可以早在之间经过时就AK

所以我们可以将所有机房按照横坐标排序

可以想到的是，我们最后肯定是要走过所有的机房，也就是说路程消耗的疲劳值是不可避免的。

我们只能尽可能的减少小ZAK所花费的时间

贪心的考虑，当我们在机房Ak所花费的时间长时，我们可能能在这个时间内AK更多的机房

所以当时间出问题时，我们肯定要取出堆顶删除以便AK更多的机房。

我们维护一个关于机房AK时间的大根堆，每次先假定要Ak,然后将时间丢入堆中，所到当前机房所花费的时间比总时间大，则移除堆顶

但是需要注意的是，移除堆顶时，我们的答案并不需要减少，因为刚刚插入一个，然后超过了总时间，在移除一个，刚刚好抵消

至于为什么只需要移除堆顶：

我在题解上看到过用while循环去移除堆顶的，然而实际并不需要，因为我们刚刚插入一个新元素

对于这个元素来说，若他不是堆中最大元素，显然我们移除最大的肯定就把这个新元素占的地方给腾出来了

若是最大元素，那么直接删除就等于过而不入，对答案没有影响

这样我们就能AC这道题

嗯好吧，其实思路是有些问题的

因为是这样的，可能的是，我们在当前这个机房，即使过而不入，单单是走过去，在加上之前的选择并AK机房耗费的时间就把总时间给超了

这样我们不得不多次弹出堆顶，同时在弹出第一个堆顶后，剩下的弹出多少个，答案数就要减去多少

好在这题没有卡

 

不会且没看stl的我选择手写二叉堆

1 #include
     
       2 #define ll long long 3 #define uint unsigned int 4 #define ull unsigned long long 5 using namespace std; 6 const int maxn = 110000; 7 struct shiki { 8     ll x, t; 9 }a[maxn];10 ll heap[maxn << 1], tot = 0, num = 0;11 ll n, m, top = 0;12 ll ans = 0; 13 14 inline ll read() {15     ll x = 0, y = 1;16     char ch = getchar();17     while(!isdigit(ch)) {18         if(ch == '-') y = -1;19         ch = getchar();20     }21     while(isdigit(ch)) {22         x = (x << 1) + (x << 3) + ch - '0';23         ch = getchar();24     }25     return x * y;26 }27 28 inline void up(int p) {29     while(p > 1) {30         if(heap[p] > heap[p / 2]) {31             swap(heap[p], heap[p / 2]);32             p /= 2;33         }34         else break;35     }36 }37 38 inline void down(int p) {39     int s = p * 2;40     while(s <= tot) {41         if(s < tot && heap[s] < heap[s + 1]) s++;42         if(heap[p] < heap[s]) {43             swap(heap[s], heap[p]);44             p = s, s = p >> 1;45         }46         else break;47     }48 }49 50 inline void extract() {51     heap[1] = heap[tot--];52     down(1);53 }54 55 inline void insert(ll k) {56     heap[++tot] = k;57     up(tot);58 }59 60 inline bool cmp(shiki a, shiki b) {61 return a.x < b.x;}62 63 inline int get_top(){
   return heap[1];}64 65 int main() {66     n = read(), m = read();67     for(int i = 1; i <= n; ++i) {68         ll x = read(), t = read();69         if(x <= m && t <= m) {70             a[++top].x = x;71             a[top].t = t;72         }73     }74     sort(a + 1, a + top + 1, cmp);75     for(int i = 1; i <= top; ++i) {76         insert(a[i].t);77         num += (a[i].x - a[i - 1].x) + a[i].t;78         if(num <= m) ans++;79         if(num > m) {80             num -= get_top();81             extract();82         }83     }84     printf("%lld\n", ans);85     return 0;86 }