题目描述

如题

题解

小根堆枚举

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;
typedef long long LL;

template <typename T>
inline void read(T &s) {
    s = 0;
    T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch))  { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w;
}

template <typename T>
inline void write(T s) {
    if (s < 0) putchar('-'), s = -s;
    if (s > 9) write(s / 10);
    putchar(s % 10 + '0');
}

namespace MakeHeap {
    int size; 
    int heap[maxn];

    inline void swap(int &aa, int &bb) { aa ^= bb ^= aa ^= bb; }

    inline void up(int p) {
        while (p > 1) {
            if (heap[p] < heap[p / 2]) {
                swap(heap[p], heap[p / 2]);
                p /= 2;
            }
            else break;
        }
    }

    inline void Insert(int val) {
        heap[++size] = val;
        up(size);
    }

    inline int GetTop() { return heap[1]; }

    inline void down(int p) {
        int s = p * 2;
        while (s <= size) {
            if (s < size && heap[s] > heap[s + 1]) ++s;
            if (heap[s] < heap[p]) {
                swap(heap[s], heap[p]);
                p = s, s = p * 2;
            }
            else break;
        }
    }

    inline void Extract() {
        heap[1] = heap[size--];
        down(1);
    }

    inline void remove(int p) {
        heap[p] = heap[size--];
        up(p), down(p);
    }

    inline bool empty() {
        return size ? false : true;
    }
}
using namespace MakeHeap;

int n;
pair <int, int> a[maxn];
LL ans;

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; ++i) {
            read(a[i].second);
            read(a[i].first);
        }
        sort(a + 1, a + n + 1);
        for (int i = 1; i <= n; ++i) {
            if (a[i].first > size) {
                Insert(a[i].second);
            }
            else if (a[i].first == size && a[i].second > GetTop()) {
                Extract();
                Insert(a[i].second);
            }
        }
        ans = 0;
        while (size > 0) {
            ans += GetTop();
            Extract();
        }
        write(ans), putchar('\n');
        size = 0; 
        memset(heap, 0, sizeof(heap));
    }
    return 0;
}