Skip to content

11287: 【原1287】工作安排

题目

题目描述

author: Xutong Chen 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1287

Description

cxt要打工赚钱。他接到了N项工作,每项工作都有自己的截止时间,第i项工作的截止日期为第Di天,如果约翰赶在这个截止时间之前完成,就可以获 得Pi元报酬,否则这些钱就没有了。约翰从第一天开始工作,完成每项工作都恰好占用一天时间。请帮助约翰计算一下,他怎么安排每天的工作,才能赚到最多的钱?

Input Format

第一行:单个整数N,1 ≤ N ≤ 10^5

第二行到N + 1行:第i + 1行有两个整数Di 和P i ,1 ≤ Di ≤ 10^9 ,1 ≤ Pi ≤ 10^9

Output Format

单个整数,表示可赚的最大钱数

Sample Input

3
2 10
1 5
1 7

Sample Output

17

hint

第一天做第三个任务,第二天做第一个任务

yyong119's solution

#include <cstdio>
#include <algorithm>
#include <queue>
#define MAX_N 100010
using namespace std;
struct Node {
    int value, day;
    bool operator <(const Node &p) const { return value > p.value; }
} a[MAX_N];
int n;
long long ans;
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}
inline bool cmp(const Node &p, const Node &q) {
    return p.day < q.day;
}

int main() {
    n = read();
    for (register int i = 0; i < n; ++i) {
        a[i].day = read(); a[i].value = read();
    }
    sort(a, a + n, cmp);
    priority_queue<Node> q;
    q.push(a[0]);
    for (register int i = 1; i < n; ++i) {
        if (a[i].day <= q.size()) {
            if (a[i].value > q.top().value) {
                q.pop(); q.push(a[i]);
            }
        }
        else q.push(a[i]);
    }
    while (!q.empty()) {
        ans += (long long)q.top().value;
        q.pop();
    }
    printf("%lld\n", ans);
    return 0;
}