求指点,用了堆排,只过了两个点
查看原帖
求指点,用了堆排,只过了两个点
73179
可期楼主2023/3/30 10:36
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<stdlib.h>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>

#define MAXN (int)1e5
#define MOD (int)1e5 + 7

using namespace std;

int h[MAXN  + 7];

void up(int i) {
    while(h[i/2] <= h[i] && i/2 >= 1){
        swap(h[i/2], h[i]);
        i /= 2;
    }
}

void down(int i, int n) {
    while((h[i * 2] >= h[i] && i * 2 <= n) || (h[i * 2 + 1] >= h[i] && i * 2 + 1 <= n)) {
        if(h[i * 2] >= h[i]) {
            swap(h[i * 2], h[i]);
            i = i * 2;
        } else if(h[i * 2 + 1] >= h[i]) {
            swap(h[i * 2 + 1], h[i]);
            i = i * 2 + 1;
        }
    }
}

// 维护一个大根堆
int main() {
    int n, b;
    scanf("%d%d", &n ,&b);
    int tail = 0;
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &h[++tail]);
        up(tail);
    }

    int h_sum = 0;
    int ans = 0;

    while(true) {
        h_sum += h[1];
        ans ++;
        if(h_sum >= b) break;
        h[1] = h[tail];
        tail --;
        down(1, tail);
    }

    cout << ans;

    return 0;
}
2023/3/30 10:36
加载中...