POJ-1456 Supermarket

Description

给定长度为\(n\)的数组\(a[]\)，每个元素\(a_i\)为\(\{p_i, d_i\}\)，其中\(p_i\)表示贡献值，\(d_i\)表示期限，每个元素的贡献需要花费\(1\)时间单位，超过期限则无法贡献。求期限内最大的总贡献值

Constraints

\(n\)不超过\(10^4\)

Solution

这道题适合作为反悔贪心的第一题

从直觉来看，按照期限\(d_i\)进行排序。维护一个小根堆，堆上按照贡献\(p_i\)作为关键字，并且假设当前时间为\(x\)，则堆大小也为\(x\)

维护反悔的过程：如果在\(d = 1\)选好了\(a_i\)，但是到了\(d = 2\)时存在2个或以上的\(a_j\)在贡献\(p_j\)上超过\(p_i\)，则执行反悔操作

Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct P {
    int p;
    int d;
    bool operator < (const P& a) const {
        if(d != a.d) return d < a.d;
        return p > a.p;
    }
};
int main() {
    for(int n; cin >> n;) {
        vector<P> vec(n);
        for(size_t i = 0 ; i < n; ++i) {
            P &v = vec[i];
            cin >> v.p >> v.d;
        }
        sort(vec.begin(), vec.end());
        int idx = 0;
        int maxd = vec.back().d;
        int ans = 0;
        priority_queue<int, vector<int>, greater<int> > que;
        for(int d = 1; d <= maxd; ++d) {
            while(idx < n && vec[idx].d < d) idx++;
            while(idx < n && vec[idx].d == d) {
                if(que.size() < d) {
                    que.push(vec[idx].p);
                } else if(que.size() == d) {
                    int smallp = que.top();
                    int curp = vec[idx].p;
                    if(smallp < curp) {
                        que.pop();
                        que.push(curp);
                    }
                }
                idx++;
            }
        }
        while(!que.empty()) {
            ans += que.top();
            que.pop();
        }
        cout << ans << endl;
    }
    return 0;
}

Link

POJ-1456 Supermarket