14006: 【原4006】Programming

题目

题目描述

author: 巢子琛 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4006

Programming

Description

dzm参加编程之美大赛，总共有n道题，每道题i有一个最晚完成时间ti，如果题目i在ti分钟内完成了，则可以得到ai的分数. 假设dzm很厉害，每道题都能在1分钟内完成，求解一个做题的安排方案，使得dzm得到的分数最高。

Input Format

第一行 一个整数n 第二行 n个整数t1~tn 保证ti<=n 第三行 n个整数a1~an n<=500

Output Format

一行一个整数，表示dzm能拿到的最高扥书

Sample Input

7
1 2 3 4 4 4 4
1 2 3 4 4 4 4

Sample Output

16

yyong119's solution

#include <cstdio>
#include <algorithm>
#include <queue>
#define MAX_N 510
using namespace std;
struct Node {
    int x, t;
    bool operator<(const Node &p) const {
        return x > p.x;
    }
} a[MAX_N];
int n, ans;
priority_queue<Node> q;
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 << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
inline bool cmp(const Node &p, const Node &q) {
    return p.t == q.t ? p.x > q.x : p.t < q.t;
}
int main() {
    n = read();
    for (register int i = 0; i < n; ++i) a[i].t = read();
    for (register int i = 0; i < n; ++i) a[i].x = read();
    sort(a, a + n, cmp);
    q.push(a[0]);
    for (register int i = 1; i < n; ++i)
        if (a[i].t > q.size())
            q.push(a[i]);
        else if (a[i].x > q.top().x) {
            q.pop();
            q.push(a[i]);
        }
    while (!q.empty()) {
        ans += q.top().x; q.pop();
    }
    printf("%d", ans);
    return 0;
}